UVa 01583-Digit Generator
For a positive integer N, its digit-sum is defined as the sum of N itself and all its individual digits. When M is the digit-sum of N, we call N a generator of M. For example, the digit-sum of 245 is 256 (= 245 + 2 + 4 + 5). Therefore, 245 is a generator of 256. However, some numbers have no generator, while others have multiple generators. For example, the generators of 216 are 198 and 207. You will write a program to find the smallest generator for a given integer.
Sample Inputs/Outputs
Sample Input(s) | Sample Output(s) |
---|---|
The first line of input contains an integer T, which represents the number of test cases. Each test case consists of an integer N (1 ≤ N ≤ 100000). | For each test case, output the smallest generator of N. If N has no generator, output '0'. |
3 216 121 2005 | 198 0 1979 |
Thought Process
Run a for loop from 1 to N-1 and check each number one by one. Convert the current number to a string, then sum its digits one by one and check if the sum equals N.
Sample Code-ZeroJudge E558: Digit Generator
#include <iostream>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
for (int i = 0; i<T; i++) {
int N;
cin >> N;
bool ok = false;
for (int j = 1; j<N; j++) {
string str = to_string(j);
int calc = j;
for (int k = 0; k<str.length(); k++) calc += str[k]-'0';
if (calc == N) {
cout << j << "\n";
ok = true;
break;
}
}
if (!ok) cout << "0\n";
}
}
//ZeroJudge E558
//Dr. SeanXD