CF 102697137 - Cheesy Numbers

Rating: -
Tags: -
Solve time: 55s
Verified: yes

Solution

Problem Understanding

A positive integer is called cheesy when it is divisible by the sum of its decimal digits. For example, the digits of 360 add up to 9, and 360 % 9 == 0, so 360 is cheesy. For 87, the digit sum is 15, but 87 % 15 != 0, so it is not cheesy. The task is simply to print YES when the condition holds and NO otherwise.

The input contains one positive integer n. The statement guarantees that n fits in a Java int, so n is at most 2,147,483,647. That means the decimal representation has at most 10 digits. We do not need an algorithm whose complexity depends on the numerical value of n, because even the largest input contains only a handful of digits.

The key edge cases are small but useful for catching careless implementations. For input 7, the digit sum is 7, and 7 % 7 == 0, so the output is YES. A solution that only considers numbers with multiple digits would fail here.

For input 10, the digit sum is 1, and every integer is divisible by 1, so the correct output is YES. A common mistake is to confuse the number of digits with the digit sum and incorrectly reject it.

For input 11, the digit sum is 2, but 11 % 2 == 1, so the output is NO. This catches implementations that accidentally check whether the digit sum divides one of the digits instead of the entire number.

Approaches

The most direct brute-force approach would be to try every possible positive divisor of n. For each candidate d, we could test whether n % d == 0, and somehow determine whether the digit sum is among those divisors. A simpler version first computes the digit sum and then tests divisibility by repeatedly considering candidates up to n. This is correct because eventually the digit sum itself is examined, but in the worst case it performs about n divisibility checks. Since n can be as large as 2,147,483,647, that is over two billion modulo operations, which is far beyond what a one-second program can afford.

The brute-force approach works because divisibility is exactly what the definition asks us to check, but it ignores the fact that the divisor is already completely determined by the digits of n. We do not need to search for it.

The key observation is that the required divisor is simply the sum of the digits. We can obtain that sum by repeatedly taking the last digit with n % 10 and removing that digit with integer division by 10. Once the sum is known, one modulo operation, n % digit_sum, gives the answer.

Because n has at most 10 decimal digits, the number of digit-processing iterations is at most 10. The optimal algorithm is thus effectively constant time under the given integer bound.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(n)	O(1)	Too slow
Optimal	O(log n)	O(1)	Accepted

Algorithm Walkthrough

Read the integer n and keep its original value. We need the original number at the final divisibility check, so the value used while extracting digits must not overwrite it permanently.
Set digit_sum to zero and repeatedly extract the last decimal digit using n % 10. Add that digit to digit_sum, then remove it with n //= 10. Each iteration processes exactly one decimal digit.
After all digits have been processed, test whether the original number is divisible by digit_sum. If the remainder is zero, print YES; otherwise, print NO.
Since the input is positive, the digit sum is also positive. There is no division-by-zero case to handle.

Why it works

The digit-extraction loop adds every decimal digit of the original number exactly once, so when it finishes, digit_sum is precisely the divisor specified by the definition of a cheesy number. The final test checks exactly whether the original number is divisible by that sum. Thus YES is printed exactly for cheesy numbers, and NO is printed for every other positive integer.

Python Solution

Pythonimport sysinput = sys.stdin.readline

def solve():    n = int(input())    original = n
    digit_sum = 0    while n > 0:        digit_sum += n % 10        n //= 10
    if original % digit_sum == 0:        print("YES")    else:        print("NO")

if __name__ == "__main__":    solve()

The variable original preserves the input because the digit-extraction loop repeatedly reduces n to zero. Without a separate copy, the final divisibility test would incorrectly test 0 % digit_sum.

The expression n % 10 obtains the last decimal digit, while n // 10 removes it. Integer division is required here because we are working with decimal digits rather than floating-point values.

The loop uses while n > 0, which is sufficient because the input is guaranteed to be positive. After the final digit is extracted, n becomes zero and the loop stops.

Python integers do not have the overflow issue that a fixed-width integer language would have, although the problem's bound is already small enough for a 32-bit signed integer.

Worked Examples

Sample 1

Input:

The digit extraction proceeds as follows.

Current `n`	Extracted digit	`digit_sum`
360	0	0
36	6	6
3	3	9
0	finished	9

The original number is 360, and the final digit sum is 9. Since 360 % 9 == 0, the program prints:

YES

This trace shows that leading zeros inside the representation cause no special problem. The zero digit is simply added to the sum like any other digit.

Sample 2

Input:

The extraction is:

Current `n`	Extracted digit	`digit_sum`
87	7	7
8	8	15
0	finished	15

Now 87 % 15 == 12, so the divisibility condition fails and the output is:

NO

The example demonstrates that calculating the digit sum and checking divisibility are separate operations. Having a nonzero digit sum does not imply that the original number is divisible by it.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log n)	Each decimal digit is processed once
Space	O(1)	Only a constant number of integer variables are used

With the given Java int bound, there are at most 10 decimal digits, so the loop executes at most 10 times. The solution is comfortably within the one-second time limit and uses negligible memory.

Test Cases

Python# helper: run solution on input string, return output stringimport sysimport io

def solve_io(inp: str) -> str:    n = int(inp.strip())    original = n
    digit_sum = 0    while n > 0:        digit_sum += n % 10        n //= 10
    return "YES\n" if original % digit_sum == 0 else "NO\n"

def run(inp: str) -> str:    return solve_io(inp)

# provided samplesassert run("360\n") == "YES\n", "sample 1"assert run("87\n") == "NO\n", "sample 2"assert run("72\n") == "YES\n", "sample 3"
# minimum-size inputassert run("1\n") == "YES\n", "single-digit number"
# all digits equalassert run("111\n") == "YES\n", "111 is divisible by 3"
# boundary case involving zeroassert run("10\n") == "YES\n", "digit sum is 1"
# maximum Java int

Test input	Expected output	What it validates
`1`	`YES`	Minimum-size positive input and single-digit divisibility
`111`	`YES`	Repeated equal digits and a nontrivial digit sum
`10`	`YES`	Zero digit and digit sum equal to one
`2147483647`	`NO`	Maximum stated input boundary

Edge Cases

For the single-digit input 7, the algorithm extracts 7, giving digit_sum = 7. The original value is also 7, so 7 % 7 == 0 and the output is YES. This works because a positive single-digit number is always divisible by its own digit sum.

For 10, the algorithm extracts 0 and then 1, producing a digit sum of 1. The final test is 10 % 1 == 0, so the output is YES. The zero digit does not cause a problem because it contributes zero to the sum.

For 11, the two extracted digits produce digit_sum = 2. The final test is 11 % 2, which is 1, so the output is NO. This confirms that the algorithm tests divisibility by the entire digit sum rather than merely checking a property of individual digits.

For the largest allowed input, 2147483647, the digit sum is 46. The algorithm performs only 10 extraction iterations, then evaluates 2147483647 % 46, which is nonzero, so the output is NO. The size of the number does not make the algorithm slower in any meaningful way because the number of decimal digits remains bounded.