N Digit Sum Even Odd

Last Updated on March 25, 2022 by Ria Pathak

CONCEPTS USED:

Recursion

DIFFICULTY LEVEL:

Hard

PROBLEM STATEMENT(SIMPLIFIED):

Given an integer N, print all N-digit numbers with sum of digits at Even index equal to sum of digits at Odd index.

See original problem statement here

For Example:

Input : N = 2

Output : 11 22 33 44 55 66 77 88 99

Explanation : 

All these elements have sum at their odd indexes and sum at their even indexes equal.

11
sum at odd indexes = element at 1st index = 1
sum at even indexes = element at 0th index = 1

Similarly, all other elements 22, 33, 44, 55, 66, 77, 88, and 99.

Can we use Recursion here ?

Yes, we need to find all combinations that satisfies the following condition. Such combinations can be easily generated using Recursion.

SOLVING APPROACH:

1. The idea is to generate all N digit combinations of digits (0-9) and check for those combinations that have sum at even indexes equal to sum at odd indexes.
2. Initialize an empty string for a combination, integers odd and even for maintaining the sum of odd and even index values, an integer flag for determining whether the current index is even or odd (0 for even / 1 for odd).
3. Now recursively keep adding digits(0-9) to the string till its length become N.
4. Simultaneously keep adding odd-indexed value to odd and even-indexed value to even.
5. When length of string becomes N, check if even is equal to odd. If Yes we get our valid combination.

NOTE: One important observation is, leading 0‘s must be
handled explicitly as they are not counted as digits.

ALGORITHM:

str = ""
flag = 0
even = 0
odd = 0

NdigitNumEO (str, n, even, odd, flag)
  if (length of str is equal to n and even is equal to odd)
    print str

  Run loop from d = '0' to '9'
    If (flag is 0)
      NdigitNumEO (str+d, n-1, even + (d - '0'), odd, 1)

    else
      NdigitNumEO (str+d, n-1, even, odd + (d - '0'), 0)

SOLUTIONS:

#include <stdio.h>
#include <string.h>

/* function for appending a char to a char array */
void append(char* s, char c) {
        int len = strlen(s);
        s[len] = c;
        s[len+1] = '\0';
}

void solve(char *s, int n, int odd, int even, int flag){
  if(n){
    char d = '0';

    char empty[] = "";
    if(strcmp(s, empty) == 0) d = '1';

    for(;d<= '9';d++){

      /* creating a temporary char array */
        char str[10];

        /* copying original char array to temp array */
        strcpy(str, s);

        /* append char i to char array str */
        append(str, d);

      if(flag)
        solve(str, n-1, odd+(d-'0'), even, 0);
      else
        solve(str, n-1, odd, even+(d-'0'), 1);  
    }
  }
  if(n == 0 && even == odd){
    printf("%s ", s);
  }
}
int main(){
  int n; scanf("%d", &n);
  char s[10] = "";
  int odd = 0;
  int even = 0;
  int flag = 0;
  solve(s, n, odd, even, flag);
  return 0;
}

#include <bits/stdc++.h>
using namespace std;

void solve(string s,int n,int odd,int even,int flag){
  if(n){
    char d = '0';
    if(s == "") d = '1';

    for(;d<= '9';d++){

      if(flag)
        solve(s+d,n-1,odd+(d-'0'),even,0);
      else
        solve(s+d,n-1,odd,even+(d-'0'),1);
    }
  }
  if(n == 0 && even == odd){
    cout<<s<<" ";
  }
}
int main(){

  int n; cin>>n;
  string s = "";
  int odd = 0;
  int even = 0;
  int flag = 0;

  solve(s, n, odd, even, flag);

  return 0;
}

import java.util.*;
import java.io.*;

public class Main {

  /* Use StringBuffer class in case we have to print large number of data
  this avoids chances of TLE */
  static StringBuffer sb = new StringBuffer();

  static void solve(String s,int n,int odd,int even,int flag){
  if(n > 0){
    char d = '0';
    if(s == "") d = '1';

    for(;d<= '9';d++){
      if(flag == 1)
        solve(s+d,n-1,odd+(d-'0'),even,0);
      else
        solve(s+d,n-1,odd,even+(d-'0'),1);
    }
  }

  if(n == 0 && even == odd){
    // Using string buffer to append each output in a string
    sb.append(s + " ");
  }
}
  public static void main(String args[]) throws IOException {

    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt(); 
    String s = "";
    int odd = 0, even = 0, flag = 0;

    solve(s, n, odd, even, flag);

    System.out.print(sb);
  }
}

def solve(s, n, odd, even, flag):
	
	if(n):
		d = '0'

		if(s == ""):
			d = '1'
		
		for d in range(10):

			if s == "":
				if d == 0:
					continue
			

			if(flag):

				solve(s + str(d), n - 1, odd + ((d)), even, 0)
			else:
				solve(s + str(d), n - 1, odd, even + ((d)), 1)
	
	if(n == 0 and even == odd):
		print(s, end = " ")


n = int(input())
s = ""
odd = 0
even = 0
flag = 0
solve(s, n, odd, even, flag)

This article tried to discuss Recursion. Hope this blog helps you understand and solve the problem. To practice more problems on Recursion you can check out MYCODE | Competitive Programming.