Problem Statement
This problem contains an image that can be viewed in the applet.
A door of a safe is locked by a password. Josh witnessed an employee opening the safe. Here is the information Josh spied.
- The password is a sequence containing exactly N digits..
- The password is entered using the keypad shown in the picture below.
- Every pair of neighboring digits in the password is adjacent on the keypad. Two digits are adjacent on the keypad if they are distinct and have a common edge.
Josh has evil intentions of unsealing the safe, but before he can realize his plan, he wants to know how many different passwords exist. Given the value for N, return the number of possible passwords that satisfy all the constraints given above.
Definition
- Class:
- UnsealTheSafe
- Method:
- countPasswords
- Parameters:
- int
- Returns:
- long
- Method signature:
- long countPasswords(int N)
- (be sure your method is public)
Constraints
- N will be between 2 and 30, inclusive.
Examples
2
Returns: 26
if the first button is 1, the second button can be either 2 or 4 if the first button is 2, the second button can be either 1, 3 or 5 if the first button is 3, the second button can be either 2 or 6 if the first button is 4, the second button can be either 1, 5 or 7 if the first button is 5, the second button can be either 2, 4, 6 or 8 if the first button is 6, the second button can be either 3, 5 or 9 if the first button is 7, the second button can be either 4, 8 or 0 if the first button is 8, the second button can be either 5, 7 or 9 if the first button is 9, the second button can be either 6 or 8 if the first button is 0, the second button can be 7 only
3
Returns: 74
25
Returns: 768478331222
4
Returns: 210
5
Returns: 600
6
Returns: 1710
7
Returns: 4882
8
Returns: 13926
9
Returns: 39746
10
Returns: 113406
11
Returns: 323638
12
Returns: 923502
13
Returns: 2635406
14
Returns: 7520334
15
Returns: 21460630
16
Returns: 61240062
17
Returns: 174759014
18
Returns: 498693678
19
Returns: 1423106470
20
Returns: 4060990974
21
Returns: 11588718614
22
Returns: 33069692814
23
Returns: 94369903558
24
Returns: 269294999646
26
Returns: 2192938314414
27
Returns: 6257916269734
28
Returns: 17857659623934
29
Returns: 50959818439094
30
Returns: 145419506315214
30
Returns: 145419506315214
29
Returns: 50959818439094