115. Two digits

How many n-digit numbers can be formed using only the digits 5 and 9, such that no three identical digits appear consecutively?

Input. One integer n (n ≤ 30).

Output. Print the number of such n-digit numbers.

Sample input	Sample output
3	6

SOLUTION

dynamic programming

Algorithm analysis

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:

f(n) = f(n – 1) + f(n – 2),

f(1) = 2, f(2) = 4

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 ≤ i ≤ 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 ≤ i ≤ 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])