A cricket player has to score N runs, with condition he can take either 1 or 2 runs only and consecutive runs should not be 2. Find all the possible combination he can take.
Examples:
Input : N = 4
Output : 4
1+1+1+1, 1+2+1, 2+1+1, 1+1+2
Input : N = 5
Output : 6
Source :Oracle Interview On campus
This problem is a variation of count number of ways to reach given score in a game and can be solved in O(n) time and constant auxiliary space.
First run scored could be either :
a) 1. Now the player has to score N-1 runs.
b) or 2. Since 2's can not be consecutive runs, next run scored has to be 1. After that, the player has to score N-(2+1) runs.
Below is the recursive solution of above problem.
Recursion relation would be:
CountWays(N) = CountWays(N-1) + CountWays(N-2)
Following recursive solution takes exponential time and space (similar to Fibonacci numbers).
C++
// A simple recursive implementation for// counting ways to reach a score using 1 and 2 with// consecutive 2 allowed#include <iostream>using namespace std;int CountWays(int n){ // base cases if (n == 0) { return 1; } if (n == 1) { return 1; } if (n == 2) { return 1 + 1; } // For cases n > 2 return CountWays(n - 1) + CountWays(n - 3);}// Driver codeint main(){ int n = 10; cout << CountWays(n); return 0;} |
Java
// A simple recursive implementation for// counting ways to reach a score using 1 and 2 with// consecutive 2 allowedimport java.io.*;class GFG { static int CountWays(int n) { // base cases if (n == 0) { return 1; } if (n == 1) { return 1; } if (n == 2) { return 1 + 1; } // For cases n > 2 return CountWays(n - 1) + CountWays(n - 3); } // Driver code public static void main(String[] args) { int n = 5; System.out.println(CountWays(n)); }} |
Python3
# A simple recursive implementation for# counting ways to reach a score using 1 and 2 with# consecutive 2 alloweddef CountWays(n): # base case if n == 0: return 1 if n == 1: return 1 if n == 2: return 1 + 1 # For cases n > 2 return CountWays(n - 1) + CountWays(n - 3)# Driver codeif __name__ == '__main__': n = 5 print(CountWays(n)) |
C#
// A simple recursive implementation// for counting ways to reach a score// using 1 and 2 with consecutive 2 allowedusing System;class GFG { static int CountWays(int n) { // base cases if (n == 0) { return 1; } if (n == 1) { return 1; } if (n == 2) { return 1 + 1; } // For cases n > 2 return CountWays(n - 1) + CountWays(n - 3); } // Driver Code static public void Main() { int n = 5; Console.WriteLine(CountWays(n)); }} |
Javascript
<script>// A simple recursive implementation for// counting ways to reach a score using 1 and 2 with// consecutive 2 allowedfunction CountWays(n, flag){ // base cases if (n == 0) { return 1; } if (n == 1) { return 1; } if (n == 2) { return 1 + 1; } // For cases n > 2 return CountWays(n - 1) + CountWays(n - 3);}// Driver codelet n = 5;document.write(CountWays(n, false));</script> |
PHP
<?php// A simple recursive implementation // for counting ways to reach a score // using 1 and 2 with consecutive 2 allowed function CountWays($n) { // base cases if ($n == 0) { return 1; } if ($n == 1) { return 1; } if ($n == 2) { return 1 + 1; } // For cases n > 2 return CountWays($n - 1) + CountWays($n - 3);} // Driver Code$n = 5; echo CountWays($n); ?> |
Output
6
We can store intermediate values and solve it in O(n) time and O(n) space.
C++
// Bottom up approach for// counting ways to reach a score using 1 and 2 with// consecutive 2 allowed#include <iostream>using namespace std;int CountWays(int n){ // noOfWays[i] will store count for value i. // 3 extra values are to take care of corner case n = 0 int noOfWays[n + 3]; noOfWays[0] = 1; noOfWays[1] = 1; noOfWays[2] = 1 + 1; // Loop till "n+1" to compute value for "n" for (int i=3; i<n+1; i++) { noOfWays[i] = // number of ways if first run is 1 noOfWays[i-1] // number of ways if first run is 2 // and second run is 1 + noOfWays[i-3]; } return noOfWays[n];}int main(){ int n = 0; cout << CountWays(n); return 0;} |
Java
import java.util.Arrays;// Bottom up approach for// counting ways to reach a score using// 1 and 2 with consecutive 2 allowedclass GfG { static int CountWays(int n) { // noOfWays[i] will store count for value i. // 3 extra values are to take care of cornser case n // = 0 int noOfWays[] = new int[n + 3]; noOfWays[0] = 1; noOfWays[1] = 1; noOfWays[2] = 1 + 1; // Loop till "n+1" to compute value for "n" for (int i = 3; i < n + 1; i++) { noOfWays[i] = // number of ways if first run is 1 noOfWays[i - 1] // number of ways if first run is 2 // and second run is 1 + noOfWays[i - 3]; } return noOfWays[n]; } public static void main(String[] args) { int n = 5; System.out.println(CountWays(n)); }} |
Python3
# Bottom up approach for# counting ways to reach a score using# 1 and 2 with consecutive 2 alloweddef CountWays(n): # noOfWays[i] will store count for value i. # 3 extra values are to take care of corner case n = 0 noOfWays = [0] * (n + 3) noOfWays[0] = 1 noOfWays[1] = 1 noOfWays[2] = 1 + 1 # Loop till "n+1" to compute value for "n" for i in range(3, n+1): # number of ways if first run is 1 # + # number of ways if first run is 2 # and second run is 1 noOfWays[i] = noOfWays[i-1] + noOfWays[i-3] return noOfWays[n]# Driver Codeif __name__ == '__main__': n = 5 print(CountWays(n)) |
C#
// Bottom up approach for// counting ways to reach a score using // 1 and 2 with consecutive 2 allowedusing System;class GfG { static int CountWays(int n) { // if this state is already visited return // its value if (dp[n, flag] != -1) { return dp[n, flag]; } // base case if (n == 0) { return 1; } // 2 is not scored last time so we can // score either 2 or 1 int sum = 0; if (flag == 0 && n > 1) { sum = sum + CountWays(n - 1, 0) + CountWays(n - 2, 1); } // 2 is scored last time so we can only score 1 else { sum = sum + CountWays(n - 1, 0); } return dp[n,flag] = sum; } // Driver code public static void Main(String[] args) { int n = 5; for (int i = 0; i <dp.GetLength(0); i++) for (int j = 0; j < dp.GetLength(1); j++) dp[i,j]=-1; Console.WriteLine(CountWays(n, 0)); }}// This code has been contributed by 29AjayKumar |
Javascript
<script>// Bottom up approach for// counting ways to reach a score using// 1 and 2 with consecutive 2 allowed function CountWays(n) { // noOfWays[i] will store count for value i. // 3 extra values are to take care of cornser case n // = 0 var noOfWays = Array(n + 3).fill(0); noOfWays[0] = 1; noOfWays[1] = 1; noOfWays[2] = 1 + 1; // Loop till "n+1" to compute value for "n" for (var i = 3; i < n + 1; i++) { // number of ways if first run is 1 // number of ways if first run is 2 // and second run is 1 noOfWays[i] = noOfWays[i - 1] + noOfWays[i - 3]; } return noOfWays[n]; } // Driver code var n = 5; document.write(CountWays(n));// This code is contributed by gauravrajput1 </script> |
Output
6
This can be further improved to O(n) time and constant space by storing only last 3 values.
C++
// Bottom up approach for// counting ways to reach a score using 1 and 2 with// consecutive 2 allowed#include <iostream>using namespace std;int CountWays(int n){ // noOfWays[i] will store count // for last 3 values before i. int noOfWays[3]; noOfWays[0] = 1; noOfWays[1] = 1; noOfWays[2] = 1 + 1; // Loop till "n+1" to compute value for "n" for (int i=3; i<n+1; i++) { noOfWays[i] = // number of ways if first run is 1 noOfWays[3-1] // number of ways if first run is 2 // and second run is 1 + noOfWays[3-3]; // Remember last 3 values noOfWays[0] = noOfWays[1]; noOfWays[1] = noOfWays[2]; noOfWays[2] = noOfWays[i]; } return noOfWays[n];}int main(){ int n = 5; cout << CountWays(n); return 0;} |
Java
// Bottom up approach for// counting ways to reach a score using 1 and 2 with// consecutive 2 allowedimport java.io.*;class GFG{static int CountWays(int n){ // noOfWays[i] will store count // for last 3 values before i. int noOfWays[] = new int[n + 3]; noOfWays[0] = 1; noOfWays[1] = 1; noOfWays[2] = 1 + 1; // Loop till "n+1" to compute value for "n" for (int i=3; i<n+1; i++) { noOfWays[i] = // number of ways if first run is 1 noOfWays[3-1] // number of ways if first run is 2 // and second run is 1 + noOfWays[3-3]; // Remember last 3 values noOfWays[0] = noOfWays[1]; noOfWays[1] = noOfWays[2]; noOfWays[2] = noOfWays[i]; } return noOfWays[n];} // Driver codepublic static void main (String[] args) { int n = 5; System.out.println(CountWays(n));}}// This code is contributed by shivanisinghss2110 |
Python3
# Bottom up approach for# counting ways to reach a score using 1 and 2 with# consecutive 2 alloweddef CountWays(n): # noOfWays[i] will store count # for last 3 values before i. noOfWays = [0] * (n+1) noOfWays[0] = 1 noOfWays[1] = 1 noOfWays[2] = 1 + 1 # Loop till "n+1" to compute value for "n" for i in range(3, n+1): # number of ways if first run is 1 # number of ways if first run is 2 # and second run is 1 noOfWays[i] = noOfWays[3-1] + noOfWays[3-3] # Remember last 3 values noOfWays[0] = noOfWays[1] noOfWays[1] = noOfWays[2] noOfWays[2] = noOfWays[i] return noOfWays[n]if __name__ == '__main__': n = 5 print(CountWays(n)) # this code is contributed by shivanisingh2110 |
C#
// Bottom up approach for// counting ways to reach a score using 1 and 2 with// consecutive 2 allowedusing System;using System.Collections.Generic;public class GFG { static int CountWays(int n) { // noOfWays[i] will store count // for last 3 values before i. int []noOfWays = new int[n + 3]; noOfWays[0] = 1; noOfWays[1] = 1; noOfWays[2] = 1 + 1; // Loop till "n+1" to compute value for "n" for (int i = 3; i < n + 1; i++) { noOfWays[i] = // number of ways if first run is 1 noOfWays[3 - 1] // number of ways if first run is 2 // and second run is 1 + noOfWays[3 - 3]; // Remember last 3 values noOfWays[0] = noOfWays[1]; noOfWays[1] = noOfWays[2]; noOfWays[2] = noOfWays[i]; } return noOfWays[n]; } // Driver code public static void Main(String[] args) { int n = 5; Console.WriteLine(CountWays(n)); }}// This code is contributed by umadevi9616 |
Javascript
<script>// Bottom up approach for// counting ways to reach a score using 1 and 2 with// consecutive 2 allowedfunction CountWays(n){ // noOfWays[i] will store count // for last 3 values before i. var noOfWays = Array(3).fill(0); noOfWays[0] = 1; noOfWays[1] = 1; noOfWays[2] = 1 + 1; // Loop till "n+1" to compute value for "n" for (var i = 3; i < n + 1; i++) { noOfWays[i] = // number of ways if first run is 1 noOfWays[3-1] // number of ways if first run is 2 // and second run is 1 + noOfWays[3-3]; // Remember last 3 values noOfWays[0] = noOfWays[1]; noOfWays[1] = noOfWays[2]; noOfWays[2] = noOfWays[i]; } return noOfWays[n];}var n = 5;document.write(CountWays(n));// This code is contributed by shivanisinghss2110 </script> |
Output
6
Approach#4: Using dynamic programming
This approach uses a dynamic programming approach to count the number of ways to reach a score of n using 1’s and 2’s such that no two consecutive 2’s are present. It uses three variables a, b, and c to store the number of ways to reach the scores i-2, i-1, and i, respectively. The loop iterates through all scores from 2 to n and updates the variables accordingly. The final count is stored in the variable c.
Algorithm
1. Initialize variables a and b to 1 and 1, respectively.
2. Initialize variable c to 0.
3. For i from 2 to n, set c to a+b.
4. Set a to b.
5. Set b to c.
6. If the last score was 2, subtract the count of ways for score n-3 from c.
7. Return c.
C++
#include <iostream>using namespace std;// Function to count the number of ways to reach a certain score in a gameint count_ways_to_reach_score(int n) { int a = 1; // Initialize a to 1, representing the number of ways to reach score 1 int b = 1; // Initialize b to 1, representing the number of ways to reach score 2 int c = 0; // Initialize c to 0, to be used as a placeholder for the number of ways to reach score i // Iterate through each score from 3 to n for (int i = 2; i <= n; i++) { c = a + b; // Calculate the number of ways to reach score i a = b; // Update a to represent the number of ways to reach score i-1 b = c; // Update b to represent the number of ways to reach score i if (i >= 3) { c -= a; // If i >= 3, subtract the number of ways to reach score i-3 to account for the fact that we can only score 3, 5, or 10 points in each move } } return c*2; // Multiply the final result by 2, since we can reach the target score either by starting with a move of 3 or 5 points}int main() { int n = 4; cout << count_ways_to_reach_score(n) << endl; // Output: 4 n = 5; cout << count_ways_to_reach_score(n) << endl; // Output: 6 return 0;} |
Java
class GFG { // Function to count the number of ways to reach a certain score in a game public static int countWaysToReachScore(int n) { int a = 1; // Initialize a to 1, representing the number of ways to reach score 1 int b = 1; // Initialize b to 1, representing the number of ways to reach score 2 int c = 0; // Initialize c to 0, to be used as a placeholder for the number of ways to reach score i // Iterate through each score from 3 to n for (int i = 2; i <= n; i++) { c = a + b; // Calculate the number of ways to reach score i a = b; // Update a to represent the number of ways to reach score i-1 b = c; // Update b to represent the number of ways to reach score i if (i >= 3) { c -= a; // If i >= 3, subtract the number of ways to reach score i-3 to account for the fact that we can only score 3, 5, or 10 points in each move } } return c * 2; // Multiply the final result by 2, since we can reach the target score either by starting with a move of 3 or 5 points } public static void main(String[] args) { int n = 4; System.out.println(countWaysToReachScore(n)); // Output: 4 n = 5; System.out.println(countWaysToReachScore(n)); // Output: 6 }} |
Python3
def count_ways_to_reach_score(n): a = 1 b = 1 c = 0 for i in range(2, n+1): c = a + b a = b b = c if i >= 3: c -= a return c*2n = 4print(count_ways_to_reach_score(n)) # Output: 4n = 5print(count_ways_to_reach_score(n)) # Output: 6 |
C#
using System;class GFG { // Function to count the number of ways to reach a // certain score in a game static int CountWaysToReachScore(int n) { int a = 1; // Initialize a to 1, representing the // number of ways to reach score 1 int b = 1; // Initialize b to 1, representing the // number of ways to reach score 2 int c = 0; // Initialize c to 0, to be used as a // placeholder for the number of ways to // reach score i // Iterate through each score from 3 to n for (int i = 2; i <= n; i++) { c = a + b; // Calculate the number of ways to // reach score i a = b; // Update a to represent the number of // ways to reach score i-1 b = c; // Update b to represent the number of // ways to reach score i if (i >= 3) { c -= a; // If i >= 3, subtract the number of // ways to reach score i-3 to // account for the fact that we can // only score 3, 5, or 10 points in // each move } } return c * 2; // Multiply the final result by 2, since we // can reach the target score either by // starting with a move of 3 or 5 points } static void Main() { int n = 4; Console.WriteLine(CountWaysToReachScore(n)); n = 5; Console.WriteLine(CountWaysToReachScore(n)); }} |
Javascript
// Function to count the number of ways to reach a certain score in a gamefunction countWaysToReachScore(n) { let a = 1; // Initialize a to 1, representing the number of ways to reach score 1 let b = 1; // Initialize b to 1, representing the number of ways to reach score 2 let c = 0; // Initialize c to 0, to be used as a placeholder for the number of ways to reach score i // Iterate through each score from 3 to n for (let i = 2; i <= n; i++) { c = a + b; // Calculate the number of ways to reach score i a = b; // Update a to represent the number of ways to reach score i-1 b = c; // Update b to represent the number of ways to reach score i if (i >= 3) { c -= a; // If i >= 3, subtract the number of ways to reach score i-3 to account for the fact that we can only score 3, 5, or 10 points in each move } } return c * 2; // Multiply the final result by 2, since we can reach the target score either by starting with a move of 3 or 5 points}// Main functionfunction main() { let n = 4; console.log(countWaysToReachScore(n)); // Output: 4 n = 5; console.log(countWaysToReachScore(n)); // Output: 6}main(); |
Output
4 6
Time Complexity: O(n)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
