Look & Say Sequence

Easy
0/40
Average time to solve is 10m
profile
Contributed by
3 upvotes
Asked in company
MAQ Software

Problem statement

You have been given a positive integer N. Your task is to find the Nth term of the Look-And-Say sequence.

The Look-And-Say sequence is a sequence of positive integers. The sequence is as follows:

1, 11, 21, 1211, 111221, 312211, 13112221,...

This sequence is constructed in the following way:

The first number is 1.

This is read as “One 1”. 
Hence, the second number will be 11.

The second number is read as “Two 1s”. 
Hence, the third number will be 21.

The third number is read as “One 2, One 1”. 
Hence, the fourth number will be 1211.

The fourth term is read as “One 1, One 2, Two 1s”.
Hence, the fifth term will be 111221. And so on.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains a single integer T, representing the number of test cases or queries to be run. The 'T' test cases follow 

For each test case, the only line contains a single integer N.
Output Format: 
For each test case/query, print the N-th term of the sequence.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 100
1 <= N <= 40

Time Limit: 1 sec
Sample Input 1:
3
1
2
3
Sample Output 1:
1
11
21
Explanation for Sample 1:
The first term is 1.
The second term is 11.
The third term is 21.
Sample Input 2:
1
6
Sample Output 2:
312211
Hint

Notice that to find the i-th sequence number, you only need the (i-1)th sequence number. Now, try dividing the (i-1)th number into blocks of same digits, obtain the length of each block, and construct the ith number using this information. Apply this recursively.

Approaches (2)
Recursive apporach

Let’s say our current number in the sequence is ‘1112213’. We divide them into blocks ‘111’, ‘22’, ‘1’ and ‘3’. There are 3 ones, 2 twos, 1 one and 1 three. Representing it with a string would look like: “31221113”.

 

Our primary task is to find all such blocks of consecutively occurring same digits, find the number of times they occur and add it to the string.

 

  • While iterating over the current number (as a string), let us maintain a variable ‘count’, which keeps count of the times the last character has occurred consecutively.
  • If the current character does not match the character before it, that means we have reached the end of the block.
  • We push this count and the previous character to the new string, which will be our next number.
  • We implement this algorithm recursively, on the newly obtained number, until we reach the Nth element. The base case will be when N = 1, for which we simply return the first term, “1”.
Time Complexity

O(2^(N/2)), where N is the given sequence index.

 

Discussing the time complexity for this problem is quite interesting. Let us first decide a loose upper bound for it. 

 

Consider the ith number in the sequence. In the worst case, there will be no adjacent digits which will be the same. Let’s suppose the number is 12123. There are 5 blocks of consecutively occurring same digits, hence, in the (i+1)th number, including the count of the blocks, there will be 2*5 = 10 digits. Assuming this the worst case for all possible numbers of the sequence, we notice that the size of the string increases exponentially, by a factor of 2. 

 

Now, calculating the (i+1)th number takes O(L) time, where L is the length of the ith number.

 

Hence, to obtain the nth number, time required would be 1 + 2 + 2^2 + 2^3 +...+ 2^(N-1) = 2^N - 1 = O(2^N).

 

An even deeper analysis indicates that a closer upper bound is O(2^N/2), but it is outside the scope of this discussion.

Space Complexity

O(2^(N/2)), where N is the given sequence index.

 

As discussed earlier, the size of the Nth number in the worst case will be O(2^N/2). The recursion stack contributes O(N) space, but since the 2^N/2 term dominates the N term, we don’t include it in the final complexity.

Code Solution
(100% EXP penalty)
Look & Say Sequence
Full screen
Console