Groupon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
def sum_(s1, s2):
first = s1
second = s2
len_diff = len(s1) - len(s2)
if len(s1) < len(s2):
first = s2
second = s1
len_diff = len(s2) - len(s1)
result = ''
carry = 0
for i in range(0, len(second)):
val = int(first[len(first) - 1 - i]) + int(second[len(second) - 1 - i]) + carry
carry = val / 10
result = str(val % 10) + result
for i in range(0, len_diff):
result = first[len_diff - i - 1] + result
return result
print sum_('1123123129', '34234234234')
print 1123123129 + 34234234234
add_num = (num1,num2)->
sum = []
carry = 0
{mynum1,mynum2} = if num1.length >= num2.length then mynum1: num1, mynum2: num2 else mynum1: num2, mynum2: num1
mynum1 = mynum1.slice()
mynum2 = mynum2.slice()
for i in [mynum1.length-1..0]
x2 = mynum2.pop()
x2 = 0 if x2 is undefined
x1 = mynum1.pop()
sum.push ((x1+x2+carry)%10)
carry = Math.floor((x1+x2)/10)
sum.push carry if carry > 0
sum.reverse()
num1 = [1,2,3,4]
num2 = [2,3,4]
sum = add_num(num1,num2)
console.log "sum of #{num1}+#{num2} = #{sum}"
You can create a linked list of int (or suitable data type like long or long long) which will store 1 integer in parts. If this datatype can store up to some digits say (10^n) then use a single node to store 10^n - 1 digits of this integer.
say if we store 5 digits in a node.
if the two big numbers are 403433232 and 4380200
then there will be two linked list...
First: 33232->4034->null
and second: 80200->434->null
then addition will be like...
33232 + 80200 = 113432 this exceed 5 digits limit so we will take 1 as carry and will store
13432 in first node of result and
then addition of second nodes will be
4034+434+1(carry from previous node) = 4469
so the result list will be
result: 13432->4469->null
i.e. 446913432
def big_add(a, b):
"""
Add two big numbers that cannot be stored using regular integers.
Both numbers must be positive.
"""
assert int(a) >= 0 and int(b) >= 0, 'numbers must be positive'
digits_a, digits_b = str(int(a)), str(int(b))
pad = max(len(digits_a), len(digits_b)) + 1 # add one more for final carry
digits_a = reversed(digits_a.zfill(pad))
digits_b = reversed(digits_b.zfill(pad))
def adder(acc, next_tup):
added, carry = acc
a, b = next_tup
summed = int(a) + int(b) + carry
return (str(summed % 10) + added, summed / 10)
added = reduce(adder, zip(digits_a, digits_b), ('', 0))
assert added[1] == 0, 'result must not have carry'
res = added[0]
if res[0] == '0' and len(res) > 1: # strip first zero if result is > 0
res = res[1:]
return res
or just a + b in Python :)
Arbitrary precision integer can be used.
For example:
BigInteger value1 = new BigInteger( String.valueOf(Long.MAX_VALUE) + String.valueOf(Long.MAX_VALUE));
BigInteger value2 = new BigInteger( String.valueOf(Long.MAX_VALUE) + String.valueOf(Long.MAX_VALUE));
BigInteger sum = value1.add( value2 );
use string.
- raihanruhin May 08, 2013