Count ways to reach a score using 1 and 2 with no consecutive 2s

Namachila October 13, 2025

0 0 14 minutes read

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 code
int 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 allowed
 
import 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 allowed
 
 
def 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 code
if __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 allowed
using 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 allowed
 
 
function 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 code
 
let 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

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 allowed
class 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 allowed
 
 
def 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 Code
if __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 allowed
using 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

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 allowed
import 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 code
public 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 allowed
def 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 allowed
using 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 allowed
function 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

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 game
int 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*2
 
n = 4
print(count_ways_to_reach_score(n)) # Output: 4
 
n = 5
print(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 game
function 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 function
function 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 zambiatek!