Algorithm implemented in ruby to add one to a number represented as an array

Question

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

Answer 1

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).

Answer 2

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.