Skip to content

Instantly share code, notes, and snippets.

@zamar-roura
Last active August 1, 2022 19:34
Show Gist options
  • Save zamar-roura/5ec17c33d57bb88035d46a8e58e9bb8c to your computer and use it in GitHub Desktop.
Save zamar-roura/5ec17c33d57bb88035d46a8e58e9bb8c to your computer and use it in GitHub Desktop.
Given an integer n, count the total number of 1 digits appearing in all non-negative integers less than or equal to n.
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment