Leading Digits of a Multiplication Table
National Olympiad — Municipal round (2025 season)
Submission name: digit.cpp
Problem summary
Count leading digits 1…9 among all products i×j for 1≤i≤m and 1≤j≤n.
Input
m n.
Output
Nine counts for leading digits 1 through 9.
Constraints
2<m,n<2000.
Worked example
Input and output for the worked example discussed below.
Input
3 5
Output
4 2 2 2 1 2 0 1 1
Solution analysis
- A number starts with d exactly when it belongs to [d×10^k,(d+1)×10^k−1] for some k≥0. These intervals partition positive integers by leading digit and length.
- Fix row i. Its valid columns for one interval satisfy ceil(low/i)≤j≤floor(high/i), intersected with 1…n. Add the intersection length instead of visiting products one by one.
- The 3×5 table has rows [1,2,3,4,5], [2,4,6,8,10], [3,6,9,12,15]. Its frequencies are 4,2,2,2,1,2,0,1,1, matching the interval counts.
Why it works
Every product belongs to exactly one tested interval. Division by the positive row index transforms that interval into precisely its allowable column indices, so counting the integer intersection counts every entry once.
Complexity: O(9m log10(mn)) time and O(9) auxiliary space.
Watch out. Use integer ceiling division at the lower endpoint. Products ending in zero still have a nonzero leading digit. Ignore empty intersections.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<array>
#include<iostream>
using namespace std;
int main(){
int m;
int n;
cin>>m>>n;
array<int,10>count{};
for(int row=1;row<=m;row++){
for(int power=1;power<=m*n;power*=10){
for(int digit=1;digit<=9;digit++){
int low=digit*power;
int high=(digit+1)*power-1;
// Convert each product interval into its column interval.
int first=max(1,(low+row-1)/row);
int last=min(n,high/row);
if(first<=last){
count[digit]+=last-first+1;
}
}
}
}
for(int digit=1;digit<=9;digit++){
if(digit>1){
cout<<' ';
}
cout<<count[digit];
}
cout<<'\n';
}