9

I need advice on my ruby based solution to a problem on Interviewbit. The problem is as follows

Given a non-negative number represented as an array of digits,

add 1 to the number ( increment the number represented by the digits ).

The digits are stored such that the most significant digit is at the head of the list. There can be upto 10,000 digits in the input array.

Example:

If the vector has [1, 2, 3]

the returned vector should be [1, 2, 4]

as 123 + 1 = 124.

My first solution was as follows

 def plusOne(a)
        new_number = a.join.to_i + 1
        result = []
        while new_number > 0
            result.push new_number%10
            new_number /= 10
        end
        result.reverse
 end

This algorithm seems correct, it passed the test inputs but on submission it gives a 'Time Limit Exceeded'. My second solution was a successful submission and is as follows.

def plusOne(a)
      carry = 1
      start_index = a.size - 1
      temp_result = []
      ans = []

      for i in start_index.downto(0)
            sum = a[i] + carry
            carry = sum/10
            temp_result.push sum%10
      end
      temp_result.push carry

      start_index = temp_result.size - 1
      while start_index >= 0 and temp_result[start_index] == 0
          start_index -= 1
      end

      while start_index >= 0
          ans.push temp_result[start_index]
          start_index -= 1
      end
      ans
    end

My first solution seems to be O(n) to me as we are just iterating over the digits in the number. So, can someone please tell me why it could have exceeded the time limit ?

Thank You

Improve this question
1
  • @JörgWMittag : Note that Integer#digits returns the least significant digit at the head of the array. Commented Jan 22, 2017 at 12:43

3 Answers 3

Reset to default
6 
while new_number > 0
    result.push new_number%10
    new_number /= 10
end

Even though at first glance this loop seems to be O(n), it is at least Ω(n²).

Since big numbers in Ruby are stored and processed as arrays of binary digits (digits in base 2³²), division by 10 is a costly operation. The exact time complexity depends on the division algorithm Ruby uses, but new_number /= 10 will have to process all of the new_number's binary digits, so it cannot be faster than O(n).

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

That makes sense, thanks for the explanation. I was suprised to notice the while loop being so slow.
You can avoid reversing the array at the end by replacing push with unshift. You might also speed this up by using Integer#divmod: new_number = 123; result = []; while new_number > 0; new_number, remainder = new_number.divmod(10); result.unshift(remainder); end; result #=> [1,2,3].
@CarySwoveland: unshift is slower than push, so you don't gain any time by doing so. divmod appears to be twice as fast as new_number /= 10
3

Solution

Note that O(n) should be your worst case scenario (e.g. with [9]*n).

For [1,2,3]*1000, the operation can be done in 1 step, since there's no carry and you'd just need to calculate 3+1.

In your first method, the while loop seems to be very expensive.

Just using :

(a.join.to_i+1).to_s.chars.map{|i| i.to_i}

is much faster, according to fruity.

Faster solution

if it's acceptable to modify the original array :

class Solution
  # param a : array of integers
  # return a array of integers
  def plusOne(a)
    a.unshift(0)
    carry = 1
    (a.size-1).downto(0) do |index|
      if a[index] < 9
        a[index] += carry
        break
      else
        a[index] = 0
      end
    end
    a.shift while a[0] == 0
    a
  end
end

It passed the test on www.interviewbit.com, and fruity tells me it's 45 times faster than your second method and 180 times faster than your first one.

Improve this answer

2 Comments

Have you benchmarked (a.join.to_i + 1).digits also for comparison?
Yes, it's really slow. It also returns the digits in the reversed order. For [9] * 10000, (a.join.to_i+1).to_s.chars.map{|i| i.to_i} is 13 times faster than (a.join.to_i+1).digits.reverse.
0 
def add_1(arr)
  idx = arr.rindex { |n| n < 9 }
  return [1].concat([0]*arr.size) if idx.nil?
  arr.map.with_index do |n,i|
    case i <=> idx
    when -1 then n
    when 0 then n+1
    else 0
    end
  end
end

add_1 [1, 2, 3]
  #=> [1, 2, 4] 
add_1 [1, 2, 9]
  #=> [1, 3, 0] 
add_1 [1, 9, 9]
  #=> [2, 0, 0] 
add_1 [9, 9, 9]
  #=> [1, 0, 0, 0]

This could also be written

def add_1(arr)
  idx = arr.rindex { |n| n < 9 }
  return [1].concat([0]*arr.size) if idx.nil?
  (arr[0,idx] << arr[idx]+1).concat([0]*(arr.size-idx-1))
end

which may be more efficient.

Improve this answer

2 Comments

It works fine, but fruity tells me it's about 100x times slower than my code for a = [1,2,3] * 100 or a = [9] * 1000
@Eric, I added an alternative that may be more efficient, but when comparing efficiency note that I've not mutated the original array. Of the two I think the former reads better, and may well be acceptable efficiency-wise.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.