"Interview question of the week" from Cassidy Williams 31-Jul-2022

index.py

# algorithm idea
# The number of times 1 is in the 1s place is the total number of 10s in the number, plus a potential bonus 1
# The number of times 1 is in the 10s place is ten times the total number of 100s in the number, plus a potential bonus 10
# ...
# The number of times 1 is in the (10**x)s place is 10**x times the total number of 10**(x+1) in the number, plus a potential bonus 10**x
def process_more_efficiently(num):
    if num <= 0:
        return 0
    string_rep_of_num = str(num)

    num_digits = len(string_rep_of_num)
    total_ones = 0
    for exponent in range(0, num_digits):
        multiplier = 10**exponent
        divisor = 10 ** (exponent + 1)
        quotient_with_no_remainder = num // divisor
        first_addition_of_ones = multiplier * quotient_with_no_remainder
        total_ones += first_addition_of_ones

        bonus_base = num % divisor
        max_bonus = multiplier
        if bonus_base >= 2 * multiplier:
            total_ones += max_bonus
        elif bonus_base >= multiplier:
            total_ones += 1 + (bonus_base % multiplier)

    return total_ones


tests = [
    1,
    2,
    9,
    10,
    11,
    13,
    15,
    16,
    17,
    18,
    19,
    20,
    21,
    22,
    10_023,
    12_345,
    1_000_000,
    1_234_567_890,
]
for test in tests:
    result = process_more_efficiently(test)
    print(
        f"There are {result:,} one-digits in every integer less than or equal to {test:,}"
    )

output.txt

There are 1 one-digits in every integer less than or equal to 1
There are 1 one-digits in every integer less than or equal to 2
There are 1 one-digits in every integer less than or equal to 9
There are 2 one-digits in every integer less than or equal to 10
There are 4 one-digits in every integer less than or equal to 11
There are 6 one-digits in every integer less than or equal to 13
There are 8 one-digits in every integer less than or equal to 15
There are 9 one-digits in every integer less than or equal to 16
There are 10 one-digits in every integer less than or equal to 17
There are 11 one-digits in every integer less than or equal to 18
There are 12 one-digits in every integer less than or equal to 19
There are 12 one-digits in every integer less than or equal to 20
There are 13 one-digits in every integer less than or equal to 21
There are 13 one-digits in every integer less than or equal to 22
There are 4,037 one-digits in every integer less than or equal to 10,023
There are 8,121 one-digits in every integer less than or equal to 12,345
There are 600,001 one-digits in every integer less than or equal to 1,000,000
There are 1,429,355,270 one-digits in every integer less than or equal to 1,234,567,890