在ruby中实现的算法,将一个数字添加到表示为数组的数字中

我需要有关Interviewbit问题的基于ruby的解决方案的建议.问题如下

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. 

我的第一个解决方案如下

 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

这个算法似乎是正确的,它通过了测试输入,但在提交时它给出了"超出时间限制".我的第二个解决方案是成功提交,如下所示.

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

我的第一个解决方案似乎是O(n),因为我们只是迭代数字中的数字.所以,有人可以告诉我为什么它可能超过了时间限制？

谢谢

while new_number > 0
    result.push new_number%10
    new_number /= 10
end

即使乍一看这个循环似乎是O(n),但至少是这样?(n²).

由于Ruby中的大数字被存储和处理为二进制数字的数组(基数为2 32的数字),因此除法10是一项代价高昂的操作.确切的时间复杂度取决于Ruby使用的除法算法,但new_number /= 10必须处理所有new_number的二进制数字,因此它不能快于O(n).