Problem
Given a number of N-digits A,
I want to find the next least N-digit number B having the same sum of digits as A,
if such a number exists.
The original number A can start with a 0.
For ex: A-> 111 then B-> 120,
A->09999 B-> 18999,
A->999 then B-> doesn't exist.
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find the next least N-digit number B having the same sum of digits as A
Created Date : 20-06-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <iterator>
using namespace std;
bool FindNextDigits(int* arr, int len)
{
for(int i = 0; i < len - 1; ++ i){
if(arr[i] + arr[i + 1] == 18 || arr[i] + arr[i + 1] == 0){
continue;
}
if(arr[i+1] == 9 || arr[i] == 0){
arr[i] ++;
arr[i+1] --;
}
else{
arr[i] --;
arr[i+1] ++;
}
return true;
}
return false;
}
void PrintArray(int *arr, int len)
{
for(int i = len - 1; i >=0; --i){
cout << arr[i];
}
cout << endl;
}
int main(int argc, char* argv[])
{
int arr[20] = {1, 1, 1};
int len( 3);
cout << "Input " << endl;
PrintArray(arr, len);
bool found = FindNextDigits(arr, len);
if(found) {
cout << "Output " << endl;
PrintArray(arr, len);
}
else{
cout << "None exists." << endl;
}
cout << "----------------" << endl;
arr[0] = 9;
arr[1] = 9;
arr[2] = 9;
arr[3] = 9;
arr[4] = 0;
len = 5;
cout << "Input " << endl;
PrintArray(arr, len);
found = FindNextDigits(arr, len);
if(found) {
cout << "Output " << endl;
PrintArray(arr, len);
}
else{
cout << "None exists." << endl;
}
cout << "----------------" << endl;
arr[0] = 9;
arr[1] = 9;
arr[2] = 9;
len = 3;
cout << "Input " << endl;
PrintArray(arr, len);
found = FindNextDigits(arr, len);
if(found) {
cout << "Output " << endl;
PrintArray(arr, len);
}
else{
cout << "None exists." << endl;
}
cout << "----------------" << endl;
for(int i = 1; i < 10; ++i){
for(int j = 0; j < i; ++j){
arr[j] = rand() % 10;
}
len = i;
cout << "Input " << endl;
PrintArray(arr, len);
found = FindNextDigits(arr, len);
if(found) {
cout << "Output " << endl;
PrintArray(arr, len);
}
else{
cout << "None exists." << endl;
}
cout << "----------------" << endl;
}
return 0;
}
Output
Input
111
Output
120
----------------
Input
09999
Output
18999
----------------
Input
999
None exists.
----------------
Input
1
None exists.
----------------
Input
47
Output
56
----------------
Input
490
Output
481
----------------
Input
4288
Output
4297
----------------
Input
17155
Output
17164
----------------
Input
167251
Output
167260
----------------
Input
6122324
Output
6122333
----------------
Input
29816758
Output
29816767
----------------
Input
332134597
Output
332134588
----------------
Press any key to continue . . .