Minimum Product of Leading Digits
National Olympiad — National round (2009 season)
Submission name: product.cpp
Problem summary
Find the minimum product of first decimal digits across M consecutive input values.
Input
N, then M, then N integers.
Output
The minimum product.
Constraints
0 < M < N <50;M<18; values10…1000000.
Worked example
Input and output for the worked example discussed below.
Input
6 3 345 67 2221 2346 23 15673
Output
4
Solution analysis
- Extract each leading digit by dividing by10 until the value is below10. Only this digit matters to later candidate products.
- For each start0…N−M, directly multiply the M corresponding digits. N<50 and M<18 make direct enumeration clear and sufficient; use long long for up to9^17.
- The sample becomes[3,6,2,2,2,1]. The four products36,24,8,4 have minimum4. Sorting would change which elements are consecutive.
Why it works
Every allowed block has one enumerated start, and each loop multiplies exactly its required leading digits. Taking the minimum over all starts gives the answer.
Complexity: O(N log A+NM) time for maximum value A and O(N) space.
Watch out. Use first rather than last digits, retain input order, and initialize products to1.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<limits>
#include<vector>
using namespace std;
int main(){
int n;
int m;
cin>>n>>m;
vector<int>leading(n);
for(int&digit:leading){
cin>>digit;
while(digit>=10){
digit/=10;
}
}
long long best=numeric_limits<long long>::max();
for(int start=0;start+m<=n;start++){
long long product=1;
for(int i=start;i<start+m;i++){
// Seventeen factors of nine require more than 32 bits.
product*=leading[i];
}
best=min(best,product);
}
cout<<best<<'\n';
}