ZeroJudge E558: Digit Generator

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

Comments