Count All Zeros in a Binomial Coefficient
Autumn Tournament (2016)
Submission name: zeros.cpp
Problem summary
Compute the binomial coefficient C(N,K) exactly and count every digit0 in its decimal representation, including internal zeros.
Input
N and K.
Output
The number of zero digits in C(N,K).
Constraints
1 ≤ N ≤ 1000; 0 ≤ K ≤ N.
Worked example
Original statement sample.
Input
50 40
Output
2
Solution analysis
- Trailing-zero formulas using prime factors are insufficient: the task asks for all zero digits. For example C(50,40)=10272278170 contains one internal zero and one trailing zero.
- Use symmetry K=min(K,N−K), then build the coefficient with value=1 and value=value·(N−K+i)/i for i=1…K. Each division is exact because the intermediate value is C(N−K+i,i). Represent the integer as little-endian decimal digits.
- Multiplication scans digits from least significant to most significant with a carry. Division scans in the opposite direction, carrying the remainder into the next digit. Trim only leading zeros after division, then count digits equal to0. K=0 leaves the value1, whose zero count is0.
Why it works
By the binomial recurrence, after iteration i the stored integer equals C(N−K+i,i); its division by i is exact at every step. Decimal carry and long division preserve that exact integer. At i=K the digits are precisely C(N,K), so directly counting zero digits gives the required result.
Watch out. Count internal zeros, not only trailing zeros. Do not use floating-point factorials or built-in64-bit integers for the coefficient. Long division must run from the most significant digit; the digit vector stores the opposite order.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int main(){
int n;
int k;
cin>>n>>k;
k=min(k,n-k);
vector<int>digits{1};
for(int i=1;i<=k;i++){
int carry=0;
for(int&digit:digits){
int product=digit*(n-k+i)+carry;
digit=product%10;
carry=product/10;
}
while(carry>0){
digits.push_back(carry%10);
carry/=10;
}
int remainder=0;
// Decimal long division starts at the most significant digit.
for(int j=static_cast<int>(digits.size())-1;j>=0;j--){
int current=remainder*10+digits[j];
digits[j]=current/i;
remainder=current%i;
}
while(digits.size()>1&&digits.back()==0){
digits.pop_back();
}
}
cout<<count(digits.begin(),digits.end(),0)<<'\n';
}