Two digits (Editorial)

We begin solving the problem by considering the base cases:

• for n = 1, there are only two valid numbers: $5$ and $9$.

• for n = 2, there are only four valid numbers: $55,59,95$ and $99$.

Let $f(n)$ denote the number of valid $n$-digit numbers. Then:

• f(1) = 2;

• f(2) = 4;

Next, we construct $n$-digit numbers based on already constructed numbers of smaller length.

• Adding one digit. Take all previously constructed (n - 1)-digit numbers and append to each of them a digit different from its last digit. In this way, we obtain $n$-digit numbers ending with 559, 595, 959 and $995$. The total number of such numbers is f(n - 1).

  

• Adding two identical digits. We also include among the $n$-digit numbers those that can be obtained from (n - 2)-digit numbers by appending two fives or two nines, ensuring that no three identical digits appear consecutively at the end. That is, we also obtain numbers ending with $599$ and $955$. Thus, we get an additional f(n - 2) valid numbers.

Therefore, we obtain the following recurrence relation:

Example

There are four valid two-digit numbers: $55,59,95$ and $99$.

There are six valid three-digit numbers: 559, 595, 959, 995, 599 and $955$. They are obtained:

• from two-digit numbers: 55 → 559, 59 → 595, 95 → 959, 99 → 995

• from one-digit numbers: 5 → 599, 9 → 955

All valid four-digit numbers are obtained:

• from three-digit numbers by appending a digit different from the last one: 5595, 5959, 9595, 9959, 5995 and $9559$.

• from two-digit numbers by appending $55$ or $99$ in such a way that three identical digits do not appear consecutively: 5599, 5955, 9599 and $9955$.

Algorithm implementation

We'll store the values $f(i)$ in the array elements $m[i]$.

int m[31];

Read the input value $n$.

scanf("%d", &n);

Set the initial values: f(1) = 2 and f(2) = 4.

m[1] = 2; m[2] = 4;

Compute the values m[i]~(3 \le i \le n) using the recurrence relation.

for(i = 3; i <= n; i++) 
  m[i] = m[i-1] + m[i-2];

Print the result — the value $m[n]$.

printf("%d\n",m[n]);

Java implementation

import java.util.*;

public class Main
{
  public static int MAX = 32;    
  static int m[] = new int[MAX];

  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    m[1] = 2; m[2] = 4;
    for(int i = 3; i <= n; i++) m[i] = m[i-1] + m[i-2];
    System.out.println(m[n]);
  }
}

Python implementation

Read the input value $n$.

n = int(input())

Initialize the list $m$.

m = [0] * 31

Set the initial values: f(1) = 2 and f(2) = 4.

m[1] = 2
m[2] = 4

Compute the values m[i]~(3 \le i \le n) using the recurrence relation.

for i in range(3, n + 1):
  m[i] = m[i - 1] + m[i - 2]

Print the result — the value $m[n]$.

print(m[n])

Written By : MathModel (Hasan Saleh)

Notice that (n \le 30) which is small , if we notice that we can optimize the brute force by cancelling the invalid cases early.

We build the number digit by digit using recursion f(\text{current index},\text{last digit},\text{count of last digit in a row}) , let's denote it as f(a,b,c) in code.

Now we start the recursion starting with a=0 (meaning 0-based indexing) , $b$ can be anything initially because we don't have anything yet , b=0 is valid , now c=0 from our state.

We try both ways :

• adding a $5$ and adding a $9$

• if c<2 i.e. we can call the last digit one more time we call

  \begin{cases} f(a+1,5,c+1) \\ f(a+1,9,c+1) \\ \end{cases}

• otherwise we call

  \begin{cases} f(a+1,5,1) \\ f(a+1,9,1) \\ \end{cases}

we keep calling until a=n then we're done.

def f(a,b,c):
    if(a==n):
       return 1
    r=0
    for d in [5,9]:  
        if(d==b):
            if(c<2):
                r+=f(a+1,d,c+1)
        else:
            r+=f(a+1,d,1)
    return r

n=int(input())
print(f(0,0,0))

Complexity \mathcal{O}(1.6^n).

BONUS : prove the complexity