Digit Sum Preserved by Multiplication by Nine
National Olympiad — National round (2013 season)
Submission name: nine.cpp
Problem summary
Count integers x in [a,b] whose decimal digit sum equals the digit sum of 9x.
Input
a b.
Output
The number of qualifying values.
Constraints
Positive endpoints have at most 18 digits; a≤b; b−a≤20000000.
Worked example
Input and output for the worked example discussed below.
Input
13 99
Output
6
Solution analysis
- Compute digit sums by repeatedly taking the remainder modulo 10 and dividing by 10. Large absolute endpoints do not prevent enumeration because the interval is short.
- Only multiples of 9 can qualify: s(x)≡x modulo 9 while s(9x)≡0 modulo 9. Start at the first multiple of 9 at least a and advance by 9, still checking both exact sums.
- In [13,99], values 18,27,36,45,90,99 qualify, so the answer is 6. Divisibility by 9 is necessary but not sufficient. The product 9x stays within signed 64-bit for all permitted 18-digit x.
Why it works
The digit-sum congruence proves no solution is skipped by the reduced enumeration. Directly testing the two sums then accepts exactly the required candidates.
Complexity: O(((b−a)/9+1) log b) time and O(1) space.
Watch out. Use long long for x and 9x. Include both endpoints and do not assume every multiple of 9 qualifies.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
using namespace std;
int digitSum(long long value){
int sum=0;
while(value>0){
sum+=value%10;
value/=10;
}
return sum;
}
int main(){
long long left;
long long right;
cin>>left>>right;
int answer=0;
// Equality forces the original value to be a multiple of nine.
for(long long value=(left+8)/9*9;value<=right;value+=9){
if(digitSum(value)==digitSum(9*value)){
answer++;
}
}
cout<<answer<<'\n';
}