Member Avatar for ChPravin

Hello All,

I had this question asked to me in one of the interviews and I wasn't able to figure it out.I need to write a method CountUniqueSequences(int sum) which returns the number of unique sequences that consist of only 1's and 2's and have an element summation equal to a given N.
For example, below are all unique sequences consisting of 1's and 2's with element summation of N=4:

1 1 1 1
1 1 2
1 2 1
2 1 1
2 2

So, CountUniqueSequences(4) should return 5.

I figured out that the frequency of occurrences of 1 in case of even nos. consist of only even nos. and in case of odd nos. consist of only odd nos.Correspondingly, the frequency of occurrence of 2 gets incremented each time the frequency of occurrence of 1 decreases.

For instance,to obtain 4:
1 can be used 2 times or 4 times and 2 can be used 1 time or 0 time.

To obtain 5: 1 can be used 1,3 or 5 times and correspondingly 2 can be used 2,1 or 0 times.

Although,it's not required in the problem I know that I can permute the number to obtain all possibilities but I do not know how to form a number.
Any suggestions would be greatly appreciated.

  • 3 Contributors
  • 3 Replies
  • 114 Views
  • 22 Hours Discussion Span
  • Latest Post Latest Post by ChPravin

Dani AI

Generated

Both and are on point: the problem counts ordered compositions of N using 1s and 2s. A simple combinatorial intuition is to view 1 as a single tile and 2 as a domino; every valid sequence is a tiling of length N. That tiling viewpoint gives the standard recurrence (last piece is either a 1 or a 2) and the well-known closed-form and algorithmic toolkit for Fibonacci-type values — see Fibonacci numbers for background.

Practical notes:

  • For interview or production code, the simplest safe implementation is an iterative O(N) loop using constant memory. It is exact (Python integers are arbitrary-precision) and fast enough for N up to millions if implemented carefully.
  • For very large N (e.g., N with thousands of digits or N up to 1e18), use the fast-doubling method or matrix exponentiation to get O(log N) multiplies. Avoid using Binet's floating-point formula for exact counts because of rounding errors.

Example Python implementations:

Iterative O(N), constant space:

def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

def count_sequences(n):
    return fib(n + 1)

Fast doubling O(log N):

def fib_pair(n):
    if n == 0:
        return (0, 1)
    a, b = fib_pair(n >> 1)
    c = a * (2 * b - a)
    d = a * a + b * b
    if n & 1:
        return (d, c + d)
    else:
        return (c, d)

def count_sequences(n):
    return fib_pair(n + 1)[0]

References and caveats: fast-doubling details and identities are documented on the Fibonacci page (see the fast-doubling section). For correctness in interviews, mention the tiling/composition argument and the iterative implementation; for large-scale needs, mention fast-doubling and Python's arbitrary-precision integers.

Recommended Answers

All 3 Replies

Member Avatar for mrnutty

First correct me in this if I'm wrong.

For sum = 0 , return 0;
For sum = 1 , return 1;
For sum = 2 , return 2;
For sum = 3 , return 3;
For sum = 4 , return 5;
For sum = 5 , return 8;
For sum = 6 , return 13;


It looks like its defined by :

F(n) =
{ 0 if n = 0 }
{ 1 if n = 1 }
{ 2 if n = 2 }
{ F(n-1) + F(n-2) for n > 2 }
{ else not defined }

Thats just a guess.

Edited by mrnutty because: n/a
Member Avatar for Rashakil Fol

This is clearly (n choose 0) + (n-1 choose 1) + (n-2 choose 2) + ... which is well known to be the fibonacci function.

Member Avatar for ChPravin

Thanks for the replies! I should've figured that out :(

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.