Look and Say - Amazon Top Interview Questions


Problem Statement :


The "look and say" sequence is defined as follows: beginning with the term 1, each subsequent term visually describes the digits appearing in the previous term. The first few terms are as follows:

1
11             <- 1 one
21             <- 2 ones
1211           <- 1 two, 1 one
111221         <- 1 one, 1 two, 2 ones
312211         <- 3 ones, 2 twos, 1 one

Given an integer n, return the nth term of this sequence as a string.

Constraints

1 ≤ n ≤ 40

Example 1

Input

n = 3

Output

"21"

Example 2

Input

n = 4

Output

"1211"

Example 3

Input

n = 5

Output

"111221"


Solution :



title-img 




                        Solution in C++ :

string solve(int n) {
    string s = "1", t;
    for (int i = 1; i < n; i++) {
        for (int j = 0, k = 0; j < s.size();) {
            char c = s[k];
            k++;
            while (k < s.size() && s[k] == s[k - 1]) k++;
            t.append(to_string(k - j));
            t.push_back(c);
            j = k;
        }
        t.swap(s);
        t.clear();
    }
    return s;
}
                    




                        Solution in Python : 
                            
class Solution:
    def solve(self, n):
        s = "1"
        for _ in range(n - 1):
            temp = ""
            for x, y in groupby(s):
                temp += str(len(list(y))) + x
            s = temp
        return s


View More Similar Problems

Tree: Preorder Traversal

Complete the preorder function in the editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's preorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the preOrder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the tree's

View Solution →

Tree: Postorder Traversal

Complete the postorder function in the editor below. It received 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's postorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the postorder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the

View Solution →

Tree: Inorder Traversal

In this challenge, you are required to implement inorder traversal of a tree. Complete the inorder function in your editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's inorder traversal as a single line of space-separated values. Input Format Our hidden tester code passes the root node of a binary tree to your $inOrder* func

View Solution →

Tree: Height of a Binary Tree

The height of a binary tree is the number of edges between the tree's root and its furthest leaf. For example, the following binary tree is of height : image Function Description Complete the getHeight or height function in the editor. It must return the height of a binary tree as an integer. getHeight or height has the following parameter(s): root: a reference to the root of a binary

View Solution →

Tree : Top View

Given a pointer to the root of a binary tree, print the top view of the binary tree. The tree as seen from the top the nodes, is called the top view of the tree. For example : 1 \ 2 \ 5 / \ 3 6 \ 4 Top View : 1 -> 2 -> 5 -> 6 Complete the function topView and print the resulting values on a single line separated by space.

View Solution →

Tree: Level Order Traversal

Given a pointer to the root of a binary tree, you need to print the level order traversal of this tree. In level-order traversal, nodes are visited level by level from left to right. Complete the function levelOrder and print the values in a single line separated by a space. For example: 1 \ 2 \ 5 / \ 3 6 \ 4 F

View Solution →