Problem Statement
John thinks 4 and 7 are lucky digits, and all other digits are not lucky. A lucky number is a number that contains only lucky digits in decimal notation.
A lucky sequence is a sequence of length numbers A[0], A[1], ..., A[length - 1] that satisfies all of the following properties:
- Each number A[i] is lucky, where 0 <= i < length.
- For each i, where 0 <= i < length, there exists at least one j such that A[i] = numbers[j].
- For each i, where 0 <= i < length - 1, the last digit of A[i] is the same as the first digit of A[i + 1].
You are given a int[] numbers and an int length. Return the number of distinct lucky sequences modulo 1234567891.
Definition
- Class:
- TheLuckySequence
- Method:
- count
- Parameters:
- int[], int
- Returns:
- int
- Method signature:
- int count(int[] numbers, int length)
- (be sure your method is public)
Notes
- Two lucky sequences A[0], A[1], ..., A[length - 1] and B[0], B[1], ..., B[length - 1] are considered distinct if there exists i, 0 <= i < length, such that A[i] ≠ B[i].
Constraints
- numbers will contain between 1 and 50 elements, inclusive.
- Each element of numbers will be between 1 and 1,000,000,000, inclusive.
- length will be between 1 and 1,000,000,000, inclusive.
Examples
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}1
Returns: 2
There are only two lucky numbers among these ten integers.{47, 74, 47}3
Returns: 2
We can construct only two different sequences (47, 74, 47) and (74, 47, 74).{100, 4774, 200, 747, 300}47
Returns: 2
{44, 47, 74, 77}2
Returns: 8