Look-And-Say Sequence
Last Updated: 25 Aug, 2020
Difficulty: Easy
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.
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
Approach 1
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.
