Open in App
Not now

# Ways to represent a number as a sum of 1’s and 2’s

• Difficulty Level : Medium
• Last Updated : 08 Mar, 2022

Given a positive integer N. The task is to find the number of ways of representing N as a sum of 1s and 2s.
Examples:

```Input : N = 3
Output : 3
3 can be represented as (1+1+1), (2+1), (1+2).

Input : N = 5
Output : 8```

For N = 1, answer is 1.
For N = 2. (1 + 1), (2), answer is 2.
For N = 3. (1 + 1 + 1), (2 + 1), (1 + 2), answer is 3.
For N = 4. (1 + 1 + 1 + 1), (2 + 1 + 1), (1 + 2 + 1), (1 + 1 + 2), (2 + 2) answer is 5.
And so on.
It can be observed that it form Fibonacci Series. So, the number of ways of representing N as a sum of 1s and 2s is (N + 1)th Fibonacci number.
How?
We can easily see that the recursive function is exactly the same as Fibonacci Numbers. To obtain the sum of N, we can add 1 to N – 1. Also, we can add 2 to N – 2. And only 1 and 2 are allowed to make the sum N. So, to obtain sum N using 1s and 2s, total ways are: number of ways to obtain (N – 1) + number of ways to obtain (N – 2).
We can find N’th Fibonacci Number in O(Log n) time. Please refer to method 5 of this post.
Below is the implementation of this approach:

## C++

 `// C++ program to find number of ways to representing``// a number as a sum of 1's and 2's``#include ``using` `namespace` `std;` `// Function to multiply matrix.``void` `multiply(``int` `F, ``int` `M)``{``    ``int` `x =  F*M + F*M;``    ``int` `y =  F*M + F*M;``    ``int` `z =  F*M + F*M;``    ``int` `w =  F*M + F*M;` `    ``F = x;``    ``F = y;``    ``F = z;``    ``F = w;``}` `// Power function in log n``void` `power(``int` `F, ``int` `n)``{``    ``if``( n == 0 || n == 1)``        ``return``;``    ``int` `M = {{1,1},{1,0}};` `    ``power(F, n/2);``    ``multiply(F, F);` `    ``if` `(n%2 != 0)``        ``multiply(F, M);``}` `/* function that returns (n+1)th Fibonacci number``   ``Or number of ways to represent n as sum of 1's``   ``2's */``int` `countWays(``int` `n)``{``    ``int` `F = {{1,1},{1,0}};``    ``if` `(n == 0)``        ``return` `0;``    ``power(F, n);``    ``return` `F;``}` `// Driver program``int` `main()``{``    ``int` `n = 5;``    ``cout << countWays(n) << endl;``    ``return` `0;``}`

## Java

 `// Java program to find number of``// ways to representing a number``// as a sum of 1's and 2's``class` `GFG``{` `// Function to multiply matrix.``    ``static` `void` `multiply(``int` `F[][], ``int` `M[][])``    ``{``        ``int` `x = F[``0``][``0``] * M[``0``][``0``] + F[``0``][``1``] * M[``1``][``0``];``        ``int` `y = F[``0``][``0``] * M[``0``][``1``] + F[``0``][``1``] * M[``1``][``1``];``        ``int` `z = F[``1``][``0``] * M[``0``][``0``] + F[``1``][``1``] * M[``1``][``0``];``        ``int` `w = F[``1``][``0``] * M[``0``][``1``] + F[``1``][``1``] * M[``1``][``1``];` `        ``F[``0``][``0``] = x;``        ``F[``0``][``1``] = y;``        ``F[``1``][``0``] = z;``        ``F[``1``][``1``] = w;``    ``}` `    ``// Power function in log n``    ``static` `void` `power(``int` `F[][], ``int` `n)``    ``{``        ``if` `(n == ``0` `|| n == ``1``)``        ``{``            ``return``;``        ``}``        ``int` `M[][] = {{``1``, ``1``}, {``1``, ``0``}};` `        ``power(F, n / ``2``);``        ``multiply(F, F);` `        ``if` `(n % ``2` `!= ``0``)``        ``{``            ``multiply(F, M);``        ``}``    ``}` `    ``/* function that returns (n+1)th Fibonacci number``    ``Or number of ways to represent n as sum of 1's``    ``2's */``    ``static` `int` `countWays(``int` `n)``    ``{``        ``int` `F[][] = {{``1``, ``1``}, {``1``, ``0``}};``        ``if` `(n == ``0``)``        ``{``            ``return` `0``;``        ``}``        ``power(F, n);``        ``return` `F[``0``][``0``];``    ``}` `    ``// Driver program``    ``public` `static` `void` `main(String[] args)``    ``{``        ``int` `n = ``5``;``        ``System.out.println(countWays(n));``    ``}``}` `// This code contributed by Rajput-Ji`

## Python3

 `# Python3 program to find number of ways to``# representing a number as a sum of 1's and 2's` `# Function to multiply matrix.``def` `multiply(F, M):` `    ``x ``=` `F[``0``][``0``] ``*` `M[``0``][``0``] ``+` `F[``0``][``1``] ``*` `M[``1``][``0``]``    ``y ``=` `F[``0``][``0``] ``*` `M[``0``][``1``] ``+` `F[``0``][``1``] ``*` `M[``1``][``1``]``    ``z ``=` `F[``1``][``0``] ``*` `M[``0``][``0``] ``+` `F[``1``][``1``] ``*` `M[``1``][``0``]``    ``w ``=` `F[``1``][``0``] ``*` `M[``0``][``1``] ``+` `F[``1``][``1``] ``*` `M[``1``][``1``]` `    ``F[``0``][``0``] ``=` `x``    ``F[``0``][``1``] ``=` `y``    ``F[``1``][``0``] ``=` `z``    ``F[``1``][``1``] ``=` `w` `# Power function in log n``def` `power(F, n):` `    ``if``( n ``=``=` `0` `or` `n ``=``=` `1``):``        ``return``    ``M ``=` `[[``1``, ``1``],[``1``, ``0``]]` `    ``power(F, n ``/``/` `2``)``    ``multiply(F, F)` `    ``if` `(n ``%` `2` `!``=` `0``):``        ``multiply(F, M)` `#/* function that returns (n+1)th Fibonacci number``# Or number of ways to represent n as sum of 1's``# 2's */``def` `countWays(n):``    ``F ``=` `[[``1``, ``1``], [``1``, ``0``]]``    ``if` `(n ``=``=` `0``):``        ``return` `0``    ``power(F, n)` `    ``return` `F[``0``][``0``]` `# Driver Code``n ``=` `5``print``(countWays(n))` `# This code is contributed by mohit kumar`

## C#

 `// C# program to find number of``// ways to representing a number``// as a sum of 1's and 2's``class` `GFG``{` `    ``// Function to multiply matrix.``    ``static` `void` `multiply(``int` `[,]F, ``int` `[,]M)``    ``{``        ``int` `x = F[0,0] * M[0,0] + F[0,1] * M[1,0];``        ``int` `y = F[0,0] * M[0,1] + F[0,1] * M[1,1];``        ``int` `z = F[1,0] * M[0,0] + F[1,1] * M[1,0];``        ``int` `w = F[1,0] * M[0,1] + F[1,1] * M[1,1];` `        ``F[0,0] = x;``        ``F[0,1] = y;``        ``F[1,0] = z;``        ``F[1,1] = w;``    ``}` `    ``// Power function in log n``    ``static` `void` `power(``int` `[,]F, ``int` `n)``    ``{``        ``if` `(n == 0 || n == 1)``        ``{``            ``return``;``        ``}``        ``int` `[,]M = {{1, 1}, {1, 0}};` `        ``power(F, n / 2);``        ``multiply(F, F);` `        ``if` `(n % 2 != 0)``        ``{``            ``multiply(F, M);``        ``}``    ``}` `    ``/* function that returns (n+1)th Fibonacci number``    ``Or number of ways to represent n as sum of 1's``    ``2's */``    ``static` `int` `countWays(``int` `n)``    ``{``        ``int` `[,]F = {{1, 1}, {1, 0}};``        ``if` `(n == 0)``        ``{``            ``return` `0;``        ``}``        ``power(F, n);``        ``return` `F[0,0];``    ``}` `    ``// Driver program``    ``public` `static` `void` `Main()``    ``{``        ``int` `n = 5;``        ``System.Console.WriteLine(countWays(n));``    ``}``}` `// This code contributed by mits`

## Javascript

 ``

Output:

`8`

Time Complexity: O(logn).

Auxiliary Space: O(1).
This article is contributed by Anuj Chauhan. If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.
{"ft_lang_label":"__label__en","ft_lang_prob":0.6481597,"math_prob":0.9981312,"size":6437,"snap":"2023-14-2023-23","text_gpt3_token_len":2738,"char_repetition_ratio":0.14969687,"word_repetition_ratio":0.37942553,"special_character_ratio":0.49588317,"punctuation_ratio":0.15766051,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9995937,"pos_list":[0,1,2],"im_url_duplicate_count":[null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-03-25T04:43:43Z\",\"WARC-Record-ID\":\"<urn:uuid:49b665c3-68ee-4185-b49b-62b9afaeac59>\",\"Content-Length\":\"230792\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:ffbb15cd-144b-4497-8b20-3d667fe3e552>\",\"WARC-Concurrent-To\":\"<urn:uuid:e3383b0d-3fc2-4a99-bc62-381a687c28db>\",\"WARC-IP-Address\":\"184.25.127.143\",\"WARC-Target-URI\":\"https://www.geeksforgeeks.org/ways-to-represent-a-number-as-a-sum-of-1s-and-2s/?ref=rp\",\"WARC-Payload-Digest\":\"sha1:DZ2ZUKHLZXXA2U7WCVSBPADFRROB7HRM\",\"WARC-Block-Digest\":\"sha1:FK2XTEIMSKI2PWOPR3E6EQIZCPGTZHFC\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-14/CC-MAIN-2023-14_segments_1679296945315.31_warc_CC-MAIN-20230325033306-20230325063306-00430.warc.gz\"}"}