Terminating Decimal
National Olympiad — National round (2020 season)
Submission name: fraction.cpp
Problem summary
For 1/N, determine the number of digits in its shortest terminating decimal expansion, or report NO if its decimal expansion is infinite. For N = 1, the answer is 0.
Input
One integer N.
Output
The number of fractional digits, or NO.
Constraints
1 ≤ N ≤ 1,000,000,000.
Worked example
An independently prepared example for this explanation.
Input
8
Output
3
Solution analysis
- A fraction with denominator N terminates after k digits exactly when N divides 10^k. Since 10^k = 2^k·5^k, no prime factor other than 2 or 5 is allowed.
- Divide N repeatedly by 2 and then by 5, counting the exponents a and b. If a remaining factor exceeds 1, print NO; otherwise print max(a,b).
- For N = 8 = 2³, three decimal places suffice: multiply numerator and denominator by 125 to obtain 125/1000. For N = 20 = 2²·5, two places suffice; for 7, no power of ten is divisible by the denominator.
Why it works
After removing all powers of 2 and 5, a residual factor prevents divisibility by every power of ten. Otherwise N = 2^a·5^b divides 10^k exactly when k ≥ a and k ≥ b, whose least solution is max(a,b).
Complexity: O(log N) time and O(1) space.
Watch out. Do not perform floating point division or count displayed digits. N = 1 has no fractional digits.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
int twos = 0;
int fives = 0;
while (n % 2 == 0) {
n /= 2;
twos++;
}
while (n % 5 == 0) {
n /= 5;
fives++;
}
// A remaining prime factor cannot divide any power of ten.
if (n != 1) {
cout << "NO\n";
} else {
cout << max(twos, fives) << '\n';
}
}