Last Updated: 18 Dec, 2020

Look & Say Sequence

Easy

Asked in company

Solve now

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.

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

Solve now

Approaches

01 Approach

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”.

Solve now

02 Approach

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 iteratively until we obtain the Nth element.

Solve now