Given an integer n, count the total number of 1 digits appearing in all non-negative integers less than or equal to n.

cassidoo-259.py

import math

"""
Dirty and quick way with strings
"""
def numberOfOnesDirty(n):
    sum = 0
    for i in range(n+1):
        sum += str(i).count('1')
    return sum

"""
Knowing that
    0-9 = 1
    0-99 = 20
    0-999 = 300
    0-9999 = 4000
    it follows the formula of
        n = number of digits in the sequence
        n*(10**(n-1))

You calculate the most you can and then you calculate the rest
"""
def numberOfOnesMath(n):

    if n <= 0:
        return 0
    elif n <= 9 and n >=1:
        return 1

    # Size of the number ex: 999 = 3, 43 = 2
    digits = int(math.log10(n))

    # ex n = 754, remainder = 54
    remainder = n % (10**digits)

    # ex n = 7654, first_digit_of_n = 7
    first_digit_of_n = n // (10**digits)

    # What's explained on the function - the arithmetic sequence - n*(10**(n-1))
    full_sequence_frequency = digits*(10**(digits-1))

    """
    For example. From 100 to 199, the number will appear 100 times.
    Going above from 200, the first number of all the other 3 digit numbers (200, 225, 300, 400, etc) is never going to be one again.
    If the number is between 219 - 199, the number of ones of '1'00 will be repeated
    """
    frequency_of_ones = 1 + remainder if first_digit_of_n == 1 else 10 ** digits

    # As sumary: How many times my first one appears + [1-9] * (number of times one appears in the next 9999 sequence) + recusiverly the same
    return   frequency_of_ones + (full_sequence_frequency * first_digit_of_n)  + numberOfOnesMath(remainder)

numberOfOnesDirty(7) # 14
numberOfOnesMath(7) # 14

numberOfOnesDirty(434) # 194
numberOfOnesMath(434) # 194

numberOfOnesDirty(-224332424) #0
numberOfOnesMath(-224332424) #0

"""
Linear for Perron, give me my points
"""

def numberOfOnesPerron(n):
    sum = 0
    digits = int(math.log10(n))
    for i in reversed(range(0, digits+1)):

        if n <= 0:
            sum +=  0
            break
        elif n <= 9 and n >=1:
            sum += 1
            break

        chunk = 10 ** i
        # ex n = 7654, first_digit_of_n = 7
        first_digit_of_n = n // chunk
        # ex n = 754, remainder = 54
        remainder = n % chunk
        full_sequence_frequency = i*(10**(i-1))
        frequency_of_ones = 1 + remainder if first_digit_of_n == 1 else chunk
        sum += frequency_of_ones + (full_sequence_frequency * first_digit_of_n)
        n = remainder
    return int(sum)