Numbers Divisible by Their Digit Product
National Olympiad — Municipal round (2020 season)
Submission name: int.cpp
Problem summary
Count integers in [A,B] divisible by the product of their decimal digits. Exclude zero-product numbers because divisibility by zero is undefined.
Input
A B.
Output
The qualifying count.
Constraints
1 ≤ A ≤ B ≤ 10^9; at most 100001 integers in the interval.
Worked example
Input and output for the worked example discussed below.
Input
1 12
Output
11
Solution analysis
- The endpoints may be large but the interval is short. Enumerate only its at-most 100001 members.
- Extract digits and multiply them. If the product is zero reject the number; otherwise test number modulo product.
- In [1,12], all nine single digits qualify. Number 10 fails, while 11 and 12 qualify, giving eleven total.
Why it works
Every candidate is counted exactly when its nonzero digit product divides it.
Complexity: O((B−A+1) log B) time and O(1) space.
Watch out. Never take modulo zero and do not scan from 1 to the large endpoint.
Commented C++17 solution
An independently written complete program with standard headers.
// Every candidate is counted exactly when its nonzero digit product divides it.
#include<iostream>
using namespace std;
int main(){
long long left,right;
cin>>left>>right;
int answer=0;
for(long long number=left;number<=right;number++){
long long product=1;
for(long long remaining=number;remaining>0;remaining/=10){
product*=remaining%10;
}
if(product!=0&&number%product==0){
answer++;
}
}
cout<<answer<<'\n';
}