Find all N-digit numbers with equal sum of digits at even and odd index

Find all N-digit numbers with equal sum of digits at even and odd index. N varies from [1 to 9].


 

For example,

3-digit numbers with equal sum of digits at even and odd index


110 121 132 143 154 165 176 187 198 220 231 242 253 264 275 286 297 330 341
352 363 374 385 396 440 451 462 473 484 495 550 561 572 583 594 660 671 682
693 770 781 792 880 891 990

 

5-digit numbers with equal sum of digits at even and odd index


10010 10021 10032 10043 10054 10065 10076 10087 10098 10120 10131 10142 10153
10164 10175 10186 10197 10230 10241 10252 10263 10274 10285 10296 10340 10351
10362 10373 10384 10395 10450 10461 10472 10483 10494 10560 10571 10582 10593
10670 10681 10692 10780 10791 10890 11000 11011 11022 11033 11044 11055 11066
11077 11088 11099 11110 11121 11132 11143 11154 11165 11176 11187 11198 11220
. . .
. . .

and many more..
 

 
The idea is to use recursion. At each point in the recursion, we append digits from 0 to 9 to the partially formed number and recuse with one less digit. We also maintain a variable to store difference between even and odd digits so far in the partially formed number. If we have filled N-digits and the difference is 0, we print the number. One special case we need to handle that the number should not start with 0.

Lets solve this problem in bottom-up manner i.e. we start from first index and recursively fill the digits from left to right. This is demonstrated below in C/C++/Java –

C

Download   Run Code

C++

Download   Run Code

Java

Download   Run Code

Output:

110 121 132 143 154 165 176 187 198 220 231 242 253 264 275 286 297 330 341 352 363 374 385 396 440 451 462 473 484 495 550 561 572 583 594 660 671 682 693 770 781 792 880 891 990

 

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
d1rge
Guest
d1rge

Huh?
110
sum of odd digits: 1 + 1 = 2
sum of even digits 0 = 0

Aditya
Guest
Aditya

Consider the digits at odd/even index
sum of even digits: 1+0 = 1
sum of odd digits: 1 = 1