Last Updated: 3 Sep, 2022
Twirly Bird
Moderate
Sam is a gaming enthusiast. He loves to play Twirly Bird a lot. The game consists of ‘N’ ENERGY levels. He can choose any ENERGY level to start the game, also he can quit playing anytime he wants.
There are some rules he needs to follow while playing, which are as follows:
He can jump to any level with fewer 'ENERGY' points and a lower index (move left in array) than the current level he is standing. The overall penalty would be the Greatest Common Divisor of all ENERGY points of the levels he visited. But Sam wants to minimize his penalty so he decided to jump only on those ENERGY levels such that the overall penalty would be 1.
There could be many ways to play the game to achieve the total penalty equal to 1.
#### Help Sam to find out the total number of ways he can play the game.
As the answer may be large, return it Modulo 10^9 + 7.
Note: Sam can only move to the left in the array from any position.
Example:
Input: ‘N’ = 4 , 'ENERGY' = [1, 3, 2, 9]
Output: 7
Explanation:
Array elements represent the ENERGY points of ith level.
9 => 2
9 => 2 => 1
9 => 3 => 1
9 => 1
2 => 1
3 => 1
1 (Sam can start and end at 1)
Thus, The total number of ways to play the game = 7
Input Format :
The first line of the input contains an integer, 'N’, denoting the size of the array (Number of ENERGY levels).
The second line of each test case contains ‘N’ space-separated integers denoting elements of the array (ENERGY Points of the levels).
Output format :
Return an integer denoting the number of ways (Modulo 10^9 + 7).
Constraints :
1 <= T <= 10
1 <= N <= 500
1 <= ENERGY[i] <= 100
Time Limit: 1 sec
Approaches
The solution for the problem lies in counting the number of strictly increasing subsequences whose gcd is 1.
We will maintain a 1D array ‘subseq’ , which stores the subsequence of the array. We start by writing a recursive code that fixes the elements in the array one by one and then generates all the subsets starting from them. After the recursive call, we erase the last element from the ‘subseq’ array to generate the next subsequence.
Our base condition would be returning as soon as we reach the last index, but before returning we also check whether the subsequence stored in ‘subseq’ array is strictly increasing or not, also we have to check whether the overall gcd is 1 or not. If both conditions are satisfied we can increase our counter as we got one of the possible ways.
The steps are as follows :
- Assign count = 0
- Function isValid([int]subseq)
- For ‘idx’ in range 0 to size of ‘subseq’
- Find gcd of the whole subseq array.
- Check whether the array is strictly increasing.
- If gcd equals to 1 and array is strictly increasing,
- Return 1.
- Else
- Return 0.
- For ‘idx’ in range 0 to size of ‘subseq’
- Function TotalWays (ENERGY[int] , ‘N’ , ‘currentIdx’ , subseq[] )
- If currentIdx == N,
- Increase Count by 1, if isValid( subseq ) returns 1.
- Insert ENERGY[currentIdx] at last of subseq .
- Call TotalWays for next indexes by increasing currentIdx.
- Erase last element from subseq.
- Call TotalWays for next indexes by increasing currentIdx.
- If currentIdx == N,
- Return Count
We can observe that the gcd of any subsequence would be from 1 to 100 as the maximum value for the array element is 100. So the idea of the solution would be to store the count of the number of strictly increasing subsequences that are ending at the current index for every value of gcd.
States: 2 State DP - index and gcd.
DP[ idx ][ gc ] = Number of strictly increasing subsequences ending at the index = ‘idx’ with gcd = ‘gc’ .
Transition:Let ‘idxBefore’ be any index lesser than the current index ‘idx’ having an element value smaller than the element value at the current index, so the transition would look like this:
DP[ idx ][ gcd(array value at idx , gc) ] += DP[ idxBefore ][ gc ]
For every value of ‘gc’ in range [1,100].
The steps are as follows :
Assign the DP table with 0 initially.
- For ‘idx’ in range 0 to ‘N’-1
- Assign 1 to DP[‘idx’][ENERGY[‘idx’]] .
- For ‘idx’ in range 0 to ‘N’-1.
- For ‘idxBefore’ in range 0 to ‘idx’-1
- If ENERGY[‘idxBefore’] < ENERGY[‘idx’],
- For ‘gc’ in range 1 to 100
- (DP[‘idx’][gcd(‘gc’,ENERGY[‘idx’])] += DP[‘idxBefore’][‘gc’])%=mod
- For ‘gc’ in range 1 to 100
- If ENERGY[‘idxBefore’] < ENERGY[‘idx’],
- For ‘idxBefore’ in range 0 to ‘idx’-1
- For ‘idx’ in range 0 to ‘N’-1
- (‘TotalWays’ += DP[‘idx’][1]) %= mod
- Return ‘TotalWays’