Remaining Digits
Autumn Tournament (2008)
Submission name: digit.cpp
Problem summary
Write every integer in [a,b]. Cross out each decimal digit whose value is divisible by p1 or p2. Count the digit occurrences that remain.
Input
Four integers a, b, p1 and p2.
Output
The remaining number of digit occurrences.
Constraints
1 ≤ a ≤ b ≤ 1000; p1 and p2 are digits greater than 1.
Worked example
Original statement sample.
Input
94 106 4 5
Output
20
Solution analysis
- Process every number in the small interval independently. Repeatedly take value % 10 to obtain its last digit, then divide by 10 to remove that digit.
- A digit survives only when both remainders, digit % p1 and digit % p2, are nonzero. In particular, zero is divisible by every nonzero divisor, so zero digits are crossed out.
- For the sample, 94 and 95 each contribute one digit; 96, 97, 98, and 99 contribute 2,2,1,2. Numbers 100 through 106 contribute respectively 1,2,2,2,1,1,2. The total is 20.
Why it works
Repeated remainder and division visit every decimal digit exactly once. The conjunction rejects exactly the digits divisible by either given divisor, so each surviving occurrence contributes one and no other digit is counted.
Complexity: O((b−a+1) log(b+1)) time and O(1) extra space; each iteration removes one decimal digit.
Watch out. Count occurrences, not distinct values. The survival test uses AND, not OR. Zero digits never survive.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
using namespace std;
int main(){
int a,b,firstDivisor,secondDivisor;
cin>>a>>b>>firstDivisor>>secondDivisor;
int answer=0;
for(int number=a;number<=b;number++){
int remaining=number;
while(remaining>0){
int digit=remaining%10;
// A digit remains only if neither divisor divides it.
if(digit%firstDivisor!=0&&digit%secondDivisor!=0){
answer++;
}
remaining/=10;
}
}
cout<<answer<<'\n';
}