write a Python program that implements this (or a similar) algorithm efficiently
ID: 3806957 • Letter: W
Question
write a Python program that implements this (or a similar) algorithm efficiently and correctly calculates the number of zeros written from one to one million. appropriately comment your source code as necessary
: n 0
count 0
repeat
n n + 1
count count + the number of zeros in n
until n is 1 million
display count
Of course, how can the number of zeros in n be counted? An algorithm for this could be:
zeros 0
repeat
if n % 10 is 0
then
zeros zeros + 1
end
n n / 10
until n is 0
This algorithm checks to see if a remainder exists when n is divided by 10 (i.e., the value of the rightmost digit of n). If there is no remainder, then the right-most digit must be 0, and the counter is incremented. The number is then divided by ten (integer division) to remove the right-most digit, and the process continues until n is 0. Take, for example, the number 10,102:
n remainder quotient
10,102 2 1,010
1,010 0 101
101 1 10
10 0 1
1 1 0
#zeros 2
Explanation / Answer
- compute number of digits: len - if len = 1 : d1: return 0 - len = 2: d2_temp: count # of digits that can possibly occur when 0 is at unit's place : for e.g. 76: so numbers can be between 10 - 76: (7 - 1) + 1 = 7 : d2: sum(d2_temp, d1) - len = 3: return d3 : sum(d3_temp, d2) : compute d3_temp: : for e.g. n = 308 : get digit at 10^(len-1) : loopMax 3 : d3_temp1: count number of zeros for this loop: 1 * 100 to (loopMax -1) * 100 : (loopMax-1) * 20 : d3_temp2: for n count (#digits when zero is at units place) + (#digits when zero is at tens place) : d3_temp = d3_temp1 + d3_temp2 99 : sum( , ) : d3_temp: : loopMax: n = 99 : n/(10^1) : 9 : d3_temp1: 8 : (9-1) * (10*(len-1)) : (loopMax - 1) * 10 * (len-1) : d3_temp2: 1 : for len, count #0s in range (loopMax * 10 * (len-1)) to n : count(90, 99) : d3_temp = 8 + 1 : sum(9, 0) : 9
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.