How to find all numbers in a range that end with certain digits

user_12048332 0
Viewed 426

I need to find all numbers in a certain range that end with specific digits.

For example:

  1. find all numbers up-to 15 that end with 5. Result should be 2 because 5 and 15 end with 5.

  2. find all numbers up-to 125 that end with 12. Result should be also 2 because 12 and 112 end with 12.

I tried this brute-force code:

def findnumber(n, m):
    count = 0
    for i in range(1, m+1):
        if i%10**len(str(n)) == n:
            count += 1
    return count

print(findnumber(5,15))

But I need to make the code more efficient.

  • The legal values are: 1 <= n, m <= 10**9
python
4 Answers

edited as Tomerikoo suggested using the floordiv operator:

def findnumber(n, m):
    s = 10 ** len(str(n))
    c = m // s
    if m % s >= n:
        c += 1
    return c
user_82193910 
def findnumber(n,m):
  count = 0
  
  #so if you find the first number that ends with n then the problem after wards is 
  #simple you just have to jumpe by ten steps, so lets first find the first number that ends in 
  #which is a lot faster than checkign every entry
  
  foundTheFirst = False
  firstNumber = 1
  while(not foundTheFirst):
      #check if firstNumebr ends in n
      if firstNumber % 10 == n:
          foundTheFirst = True
          break
      firstNumber += 1
  

  for i in range(firstNumber,m+1,10):
        count+=1
  return count
print(findnumber(2,20))
user_86167240

Its a lot more simple, and can be done without iterating at all,

each 10 numbers in sequence will have one that ends with m, for example :

1 2 3 4 5 6 7 8 9 10 | 11 12 13 14 15

def findnumber(n, m):
    n_digits = 0
    n_copy = n
    while n_copy != 0:
        n_digits += 1
        n_copy //= 10

    digits = 10 ** n_digits
    count = m // digits
    if m % digits >= n:
        count += 1
    return count

print(findnumber(5, 15))
print(findnumber(35, 1400))

#  2
#  14
user_140814740

Here's efficient general algorithm: with simple assumption i.e for example, n is 5 and m is 26 then we need to check only for 5, 15, 25 which are offset by 10 i.e offset = 10 ** (total digits of n).

Here's code:

def count(n, m):
    cnt    = 0
    num    = n
    ln     = len(str(n))
    offset = 10 ** ln
    
    while num <= m:
        cnt += 1
        num += offset

    return cnt


>>> count(5, 14)
1
>>> count(5, 16)
2
>>> count(5, 25)
3
>>> count(5, 125)
13
>>> count(5, 1125)
113

which is efficient in terms of operations

user_141087340
Related