CODEWITHSUNDEEP
ruby
user6652239
user6652239

Reputation:

Extracting values without looping in Ruby

Lets say we need to extract values from range of (0..999_999_999). We need the sum of all numbers that returns true for our conditional statement. For example, the ones that have the sequence of "123" digits at the end of their numbers.

What would be the fastest way to get this sum without looping?

Edit: The conditional statement could be any, such as n.to_s.chars.map{|d| d = d.to_i}.inject(:+) % 12345 == 0 where n is the number within the range.

Edit2: Here is the code that I have trouble with:

def find_all(n, k)
    arr = []
    lower_limit = ("1" + "0" * (k - 1)).to_i
    upper_limit = ("9" * k).to_i  
    while lower_limit <= upper_limit
      if lower_limit.to_s.chars == lower_limit.to_s.chars.sort && lower_limit.to_s.chars.map{|v| v = v.to_i}.inject(:+) == n
        arr << lower_limit
      end
      lower_limit += 1
    end
    arr.empty? ? [] : [arr.size, arr.min, arr.max]
end

where n is the sum of all digits and k is the # of digits in number.

My code should run on the server in less than 12000 ms with very huge numbers of k several times with different (n,k). Even though my code works, its algorithm is too slow, looping will not result in success.

Upvotes: 0

Views: 61

Answers (1)

Cary Swoveland
Cary Swoveland

Reputation: 110725

The range is

r = 0..10**9-1

r.size
  #=> 1_000_000_000 (10**9)

For any given last three digits, this range contains 10**6 numbers ending in those three digits. Suppose those last three digits were 000. Then the sum of those numbers would be the sum of the numbers in the range 0..10**6-1 multiplied by 10**3:

s = (10**3) * (0 + 10**6-1)*(10**6)/2
  #=> 499999500000000

If the last three digits of each of the 10**6 numbers in this sum were 123, rather than 000, 123 would be added to each of those numbers. Therefore, the sum of the numbers ending 123 is

s + 123 * (10**6) 
  #=> 499999746000000

Upvotes: 2

Related Questions