Count total number of N digit numbers such that the difference between sum of even and odd digits is 1

0 0 8 minutes read

Given a number n, we need to count the total number of n digit numbers such that the sum of even digits is 1 more than the sum of odd digits. Here even and odd means positions of digits are like array indexes, for example, the leftmost (or leading) digit is considered as even digit, next to leftmost is considered as odd, and so on.

Example:

Input:  n = 2
Output: Required Count of 2 digit numbers is 9
Explanation : 10, 21, 32, 43, 54, 65, 76, 87, 98.

Input:  n = 3
Output: Required Count of 3 digit numbers is 54
Explanation: 100, 111, 122, ......, 980

We strongly recommend you to minimize your browser and try this yourself first.
This problem is mainly an extension of Count of n digit numbers whose sum of digits equals to given sum. Here the solution of subproblems depends on four variables: digits, esum (current even sum), osum (current odd sum), isEven(A flag to indicate whether the current digit is even or odd).

Below is Memoization based solution for the same.

C++

// A memoization based recursive program to count numbers
// with difference between odd and even digit sums as 1
#include<bits/stdc++.h>
  
using namespace std;
  
// A lookup table used for memoization.
unsigned long long int lookup[50][1000][1000][2];
  
// Memoization based recursive function to count numbers
// with even and odd digit sum difference as 1.  This function
// considers leading zero as a digit
unsigned long long int  countRec(int digits, int esum,
                               int osum, bool isOdd, int n)
{
    // Base Case
    if (digits == n)
        return (esum - osum == 1);
  
    // If current subproblem is already computed
    if (lookup[digits][esum][osum][isOdd] != -1)
        return lookup[digits][esum][osum][isOdd];
  
    // Initialize result
    unsigned long long int ans = 0;
  
    // If the current digit is odd, then add it to odd sum and recur
    if (isOdd)
      for (int i = 0; i <= 9; i++)
          ans +=  countRec(digits+1, esum, osum+i, false, n);
    else // Add to even sum and recur
      for (int i = 0; i <= 9; i++)
          ans +=  countRec(digits+1, esum+i, osum, true, n);
  
    // Store current result in lookup table and return the same
    return lookup[digits][esum][osum][isOdd] = ans;
}
  
// This is mainly a wrapper over countRec. It
// explicitly handles leading digit and calls
// countRec() for remaining digits.
unsigned long long int finalCount(int n)
{
    // Initialize number digits considered so far
    int digits = 0;
  
    // Initialize all entries of lookup table
    memset(lookup, -1, sizeof lookup);
  
    // Initialize final answer
    unsigned long long int ans = 0;
  
    // Initialize even and odd sums
    int esum = 0, osum = 0;
  
    // Explicitly handle first digit and call recursive function
    // countRec for remaining digits.  Note that the first digit
    // is considered as even digit.
    for (int i = 1; i <= 9; i++)
          ans +=  countRec(digits+1, esum + i, osum, true, n);
  
    return ans;
}
  
// Driver program
int main()
{
    int n = 3;
    cout << "Count of "<<n << " digit numbers is " << finalCount(n);
    return 0;
}

Java

// A memoization based recursive 
// program to count numbers with 
// difference between odd and 
// even digit sums as 1
class GFG 
{
     
// A lookup table used for memoization.
static int [][][][]lookup = new int[50][1000][1000][2];
 
// Memoization based recursive 
// function to count numbers
// with even and odd digit sum 
// difference as 1. This function
// considers leading zero as a digit
static int countRec(int digits, int esum,
                            int osum, int isOdd, int n)
{
    // Base Case
    if (digits == n)
        return (esum - osum == 1)?1:0;
 
    // If current subproblem is already computed
    if (lookup[digits][esum][osum][isOdd] != -1)
        return lookup[digits][esum][osum][isOdd];
 
    // Initialize result
    int ans = 0;
 
    // If current digit is odd, then
    // add it to odd sum and recur
    if (isOdd==1)
    for (int i = 0; i <= 9; i++)
        ans += countRec(digits+1, esum, osum+i, 0, n);
    else // Add to even sum and recur
    for (int i = 0; i <= 9; i++)
        ans += countRec(digits+1, esum+i, osum, 1, n);
 
    // Store current result in lookup 
    // table and return the same
    return lookup[digits][esum][osum][isOdd] = ans;
}
 
// This is mainly a wrapper over countRec. It
// explicitly handles leading digit and calls
// countRec() for remaining digits.
static int finalCount(int n)
{
    // Initialize number digits considered so far
    int digits = 0;
 
    // Initialize all entries of lookup table
    for(int i = 0; i < 50; i++)
        for(int j = 0; j < 1000; j++)
            for(int k = 0; k < 1000; k++)
                for(int l = 0; l < 2; l++)
                    lookup[i][j][k][l] = -1;
 
 
    // Initialize final answer
    int ans = 0;
 
    // Initialize even and odd sums
    int esum = 0, osum = 0;
 
    // Explicitly handle first digit and 
    // call recursive function countRec 
    // for remaining digits. Note that
    // the first digit is considered 
    // as even digit.
    for (int i = 1; i <= 9; i++)
        ans += countRec(digits+1, esum + i, osum, 1, n);
 
    return ans;
}
 
// Driver program
public static void main(String[] args) 
{
    int n = 3;
    System.out.println("Count of "+ n + 
            " digit numbers is " + finalCount(n));
}
}
 
// This code has been contributed by 29AjayKumar

Python3

# A memoization based recursive program to count numbers
# with difference between odd and even digit sums as 1
 
# Memoization based recursive function to count numbers
# with even and odd digit sum difference as 1. This function
# considers leading zero as a digit
def countRec(digits, esum, osum, isOdd, n):
 
    # Base Case
    if digits == n:
        return (esum - osum == 1)
 
    # If current subproblem is already computed
    if lookup[digits][esum][osum][isOdd] != -1:
        return lookup[digits][esum][osum][isOdd]
 
    # Initialize result
    ans = 0
 
    # If the current digit is odd, 
    # then add it to odd sum and recur
    if isOdd:
        for i in range(10):
            ans += countRec(digits + 1, esum, 
                            osum + i, False, n)
 
    # Add to even sum and recur
    else:
        for i in range(10):
            ans += countRec(digits + 1, esum + i, 
                            osum, True, n)
 
    # Store current result in lookup table 
    # and return the same
    lookup[digits][esum][osum][isOdd] = ans
    return ans
 
# This is mainly a wrapper over countRec. It
# explicitly handles leading digit and calls
# countRec() for remaining digits.
def finalCount(n):
    global lookup
 
    # Initialize number digits considered so far
    digits = 0
 
    # Initialize all entries of lookup table
    lookup = [[[[-1, -1] for i in range(500)]
                         for j in range(500)]
                          for k in range(50)]
 
    # Initialize final answer
    ans = 0
 
    # Initialize even and odd sums
    esum = 0
    osum = 0
 
    # Explicitly handle first digit and call 
    # recursive function countRec for remaining digits. 
    # Note that the first digit is considered as even digit
    for i in range(1, 10):
        ans += countRec(digits + 1, esum + i, 
                        osum, True, n)
 
    return ans
 
# Driver Code
if __name__ == "__main__":
     
    # A lookup table used for memoization.
    lookup = []
    n = 3
    print("Count of %d digit numbers is %d" % (n, finalCount(n)))
 
# This code is contributed by
# sanjeev2552

C#

// A memoization based recursive 
// program to count numbers with 
// difference between odd and 
// even digit sums as 1 
using System;
     
class GFG 
{
     
// A lookup table used for memoization.
static int [,,,]lookup = new int[50,1000,1000,2];
 
// Memoization based recursive 
// function to count numbers
// with even and odd digit sum 
// difference as 1. This function
// considers leading zero as a digit
static int countRec(int digits, int esum,
                    int osum, int isOdd, int n)
{
    // Base Case
    if (digits == n)
        return (esum - osum == 1)?1:0;
 
    // If current subproblem is already computed
    if (lookup[digits,esum,osum,isOdd] != -1)
        return lookup[digits,esum,osum,isOdd];
 
    // Initialize result
    int ans = 0;
 
    // If current digit is odd, then
    // add it to odd sum and recur
    if (isOdd==1)
    for (int i = 0; i <= 9; i++)
        ans += countRec(digits+1, esum, osum+i, 0, n);
    else // Add to even sum and recur
    for (int i = 0; i <= 9; i++)
        ans += countRec(digits+1, esum+i, osum, 1, n);
 
    // Store current result in lookup 
    // table and return the same
    return lookup[digits,esum,osum,isOdd] = ans;
}
 
// This is mainly a wrapper over countRec. It
// explicitly handles leading digit and calls
// countRec() for remaining digits.
static int finalCount(int n)
{
    // Initialize number digits considered so far
    int digits = 0;
 
    // Initialize all entries of lookup table
    for(int i = 0; i < 50; i++)
        for(int j = 0; j < 1000; j++)
            for(int k = 0; k < 1000; k++)
                for(int l = 0; l < 2; l++)
                    lookup[i,j,k,l] = -1;
 
 
    // Initialize final answer
    int ans = 0;
 
    // Initialize even and odd sums
    int esum = 0, osum = 0;
 
    // Explicitly handle first digit and 
    // call recursive function countRec 
    // for remaining digits. Note that
    // the first digit is considered 
    // as even digit.
    for (int i = 1; i <= 9; i++)
        ans += countRec(digits+1, esum + i, osum, 1, n);
 
    return ans;
}
 
// Driver code
public static void Main(String[] args) 
{
    int n = 3;
    Console.WriteLine("Count of "+ n + 
            " digit numbers is " + finalCount(n));
}
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
// A memoization based recursive 
// program to count numbers with 
// difference between odd and 
// even digit sums as 1
 
// A lookup table used for memoization.
let lookup = new Array(50);
for(let i=0;i<50;i++)
{
    lookup[i]=new Array(1000);
    for(let j=0;j<1000;j++)
    {
        lookup[i][j]=new Array(1000);
        for(let k=0;k<1000;k++)
        {
            lookup[i][j][k]=new Array(2);
        }
         
    }
}
 
// Memoization based recursive 
// function to count numbers
// with even and odd digit sum 
// difference as 1. This function
// considers leading zero as a digit
function countRec(digits,esum,osum,isOdd,n)
{
    // Base Case
    if (digits == n)
        return (esum - osum == 1)?1:0;
   
    // If current subproblem is already computed
    if (lookup[digits][esum][osum][isOdd] != -1)
        return lookup[digits][esum][osum][isOdd];
   
    // Initialize result
    let ans = 0;
   
    // If current digit is odd, then
    // add it to odd sum and recur
    if (isOdd==1)
    for (let i = 0; i <= 9; i++)
        ans += countRec(digits+1, esum, osum+i, 0, n);
    else // Add to even sum and recur
    for (let i = 0; i <= 9; i++)
        ans += countRec(digits+1, esum+i, osum, 1, n);
   
    // Store current result in lookup 
    // table and return the same
    return lookup[digits][esum][osum][isOdd] = ans;
}
 
// This is mainly a wrapper over countRec. It
// explicitly handles leading digit and calls
// countRec() for remaining digits.
function finalCount(n)
{
    // Initialize number digits considered so far
    let digits = 0;
   
    // Initialize all entries of lookup table
    for(let i = 0; i < 50; i++)
        for(let j = 0; j < 1000; j++)
            for(let k = 0; k < 1000; k++)
                for(let l = 0; l < 2; l++)
                    lookup[i][j][k][l] = -1;
   
   
    // Initialize final answer
    let ans = 0;
   
    // Initialize even and odd sums
    let esum = 0, osum = 0;
   
    // Explicitly handle first digit and 
    // call recursive function countRec 
    // for remaining digits. Note that
    // the first digit is considered 
    // as even digit.
    for (let i = 1; i <= 9; i++)
        ans += countRec(digits+1, esum + i, osum, 1, n);
   
    return ans;
}
 
// Driver program
let n = 3;
document.write("Count of "+ n + 
            " digit numbers is " + finalCount(n));
 
 
// This code is contributed by rag2127
 
</script>

Output:

Count of 3 digit numbers is 54

Thanks to Gaurav Ahirwar for providing above solution.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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!