current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Join the Stack Overflow Community
Stack Overflow is a community of 6.6 million programmers, just like you, helping each other.
Join them; it only takes a minute:
Sign up
up vote 7 down vote favorite
1

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

share|improve this question
    
@JörgWMittag : Note that Integer#digits returns the least significant digit at the head of the array. – Eric Duminil 19 hours ago
up vote 6 down vote 
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).

share|improve this answer
    
That makes sense, thanks for the explanation. I was suprised to notice the while loop being so slow. – Eric Duminil 18 hours ago
    
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]. – Cary Swoveland 9 hours ago
up vote 4 down vote

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.

share|improve this answer
    
Have you benchmarked (a.join.to_i + 1).digits also for comparison? – Jörg W Mittag 18 hours ago
    
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. – Eric Duminil 18 hours ago
up vote 0 down vote 
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]
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.