Código 101: Símbolo K-Th na gramática

Construímos uma tabela de n linhas (1 indexada). Começamos escrevendo 0 na 1ª linha. Now in every subsequent row, we look at the previous row and replace each occurrence of 0 with 01, and each occurrence of 1 with 10. For example, for n = 3, the 1st row is 0, the 2nd row is 01, and the 3rd row is 0110. Given two integer n and k, return the (1-indexed) symbol in the nth row of a table of n rows. Exemplo 1: entrada: n = 1, k = 1 saída: 0 Explicação: linha 1: 0 Exemplo 2: entrada: n = 2, k = 1 saída: 0 Explicação: linha 1: 0 linha 2: 01 Exemplo 3: entrada: n = 2, k = 2 saída: 1 Explicação: linha 1: 0 <= 2n – 1

You can find the question here.

By reading the question we can deduce that there is some kind of structure we need to create based on the question’s requirement. Few things to note here:

To create the structure we need to rely on previous output. So can we use recursion?
The structure is a tree.

After creating the structure mentioned we can deduce few more things.

The size of each row is double the size of previous row.
If we break down the row we can see that the previous row and the first half of the row is exactly same.
The second half of the row is the complement of the previous row

Now we will try to think of a solution keeping all these things in mind. We have previously worked on recursion solutions and we generally break it down to 3 steps.

Base Case (when to stop)
Work needed to move toward Base Case or Solution
Recursive Call (call ourselves)

Let’s start with base case, We know that at n = 1 we have zero, lets consider column as k. So at n == 1 and k == 1 we have 0. This becomes our base case.

if (n == 1 && k == 1) return 0;

We will skip second part and move to the 3rd step the recursion calls.
Based on observations we know that the solution depends on the previous output and the complement of previous output.
so can we write 2 recursive calls?

recursion( n-1, k ) -> Quando K é menos o elemento do meio // e para a segunda chamada, precisamos do complemento dos valores, ou seja, quando o K é o Great, então a recursão do elemento médio // (N -1, K -Mid) -> quando K é menos o elemento do meio que está chegando à segunda parte. Na verdade, enquanto pensamos no terceiro passo, nós gentamos a segunda parte. Vou explicar no código abaixo. public static int kthGrammar (int n, int k) {if (n == 1 && k == 1) {return 0; } int mid = ((int) pow (2, n – 1)) / 2; if (k <= mid) {return kthgrammar (n-1, k); } else {return (kthGrammar (n-1, k-mid)) ^ 1; }} Veja o código não tem mais nada, então o que discutimos, encontramos MID, chamamos as chamadas de recursão com base nas condições que conhecíamos. Espero que você entenda melhor agora, continue com a série Code101 e você terá uma melhor compreensão. #Happycoding

Fonte