Twirly Bird

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
1 upvote

Problem statement

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
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
5
2 3 1 2 4
4
1 3 2 9
Sample Output 1 :
7
7
Explanation Of Sample Input 1 :
Test 1:
The number of possible ways :
4 => 2 => 1  (Here overall penalty = 1 , but in intermediate level it is greater than 1)
4 => 1
4 => 3
4 => 3 => 2  (Jumping to the left level which has lesser ENERGY points)
2 => 1
1                 (Start and end at the same level)
3 => 2

Note that, the penalty can be greater than 1 at any intermediate level but the overall penalty should be 1.

gcd(4, 2, 1) = gcd(4,1) = gcd(4, 3) = gcd(4, 3, 2) = gcd(2, 1) = gcd( 1 ) = gcd(3, 2) = 1.

Hence the number of ways is 7. 

Test 2:
 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
Sample Input 2 :
2
3
2 3 4
2
2 4
Sample Output 2 :
3
0
Hint

Check for all Subsequences using the pick and don’t pick concept. 

Approaches (2)
Brute Force

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 :

  1. Assign count = 0
  2. 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.
  3. 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.
  4. Return Count
Time Complexity

O( N * (2^ N) ), Where ‘N’ is the number of elements in the array. 

As for every element, we recurse by fixing an element for generating the next subsequence and also checking whether it is valid or not.  

Hence the time complexity is O( N * (2 ^ N) ).

Space Complexity

O( N ) , Where ‘N’ is the number of elements in the array. 

 

As we are using another array to keep track of all subsequences by inserting and removing elements. 

Hence the space complexity is O( N ).

Code Solution
(100% EXP penalty)
Twirly Bird
Full screen
Console