Look-And-Say Sequence

Easy
0/40
Average time to solve is 15m
profile
Contributed by
100 upvotes
Asked in companies
BarclaysMicrosoftMakeMyTrip

Problem statement

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. And so on.

The fourth term is read as “One 1, One 2, Two 1s”.

Hence, the fifth term will be 111221. And so on.

Given an integer N, find the Nth term of the sequence.

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. 
Then the test cases follow.

For each test case, the only line contains a single integer 'N'.
Output Format: 
For each test case/query, print a single containing a single string denoting the Nth term of the sequence.

The output for every test case will be printed in a separate line.

Note:

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

Where 'T' is the number of test cases and 'N' is the given sequence index.

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 term, you only need the (i-1)-th sequence term. Now, try dividing the (i-1)-th term into blocks of same digits, obtain the length of each block, and construct the i-th term using this information. Apply this iteratively.

Approaches (1)
Iterative Solution

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 do this in an iterative manner until we obtain the nth element.

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 i-th term 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 term, including the count of the blocks, there will be 2*5 = 10 digits. Assuming this 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 term takes O(L) time, where L is the length of the i-th term.

 

Hence, to obtain the N-th term, 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 in the time complexity discussion, the size of the N-th term in the worst case will be O(2 ^ N / 2).

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