Last active
December 17, 2016 11:59
-
-
Save alisherafat01/2f528c3fc2b174e405f654c41e9a2b30 to your computer and use it in GitHub Desktop.
Tape equilibrium
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Tape: | |
def __init__(self, _array): | |
self.array = _array | |
if len(self.array) < 2: | |
raise Exception("array must have at least 2 items") | |
# without considering complexity -> because of using sum() function in for loop | |
def getAnswer1(self): | |
leftSum = rithtSum = 0 | |
diff = 999999999 # a big int number for the first comparison | |
for i in range(1, len(self.array)): | |
leftSum = sum(self.array[0:i]) # complexity issue | |
rithtSum = sum(self.array[i:]) # complexity issue | |
tempDiff = abs(leftSum - rithtSum) | |
if tempDiff < diff: | |
diff = tempDiff | |
return diff | |
# returns answer with considering complexity | |
def getAnswer2(self): | |
leftSum = self.array[0] | |
rithtSum = sum(self.array[1:]) # this is not inside for loop so it's ok :) | |
diff = abs(leftSum - rithtSum) | |
for i in range(1, len(self.array) - 1): | |
leftSum += self.array[i] | |
rithtSum -= self.array[i] | |
tempDiff = abs(leftSum - rithtSum) | |
if tempDiff < diff: | |
diff = tempDiff | |
return diff | |
array = [3, 1, 2, 4, 3] | |
tape = Tape(array) | |
# print tape.getAnswer1() | |
print tape.getAnswer2() # prints 1 | |
array2 = [-10, 12, -7, 4] | |
tape2 = Tape(array2) | |
# print tape2.getAnswer1() | |
print tape2.getAnswer2() # prints 5 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment