I've recently failed a coding challenge and I'd like to know the solution to the problem.
Here's what was asked of me (from memory as I do not have access to the question anymore):
Create a function that takes an array of integers and sums the first and last item, then the second and second to last, and so on. You must do this until there's only two items left in the returning array.
Example:
Input: [1, 4, 2, 3, 6, 10]
Returns: [16, 10]
Because:
[(1 10), (4 6), (2 3)] =
[11, 10, 5] =>
[(11 5), 10] =
[16, 10]
Example 2:
Input: [-1, 3, 2, -2, 11, 7, -9]
Returns: [-12, 23]
Because:
[(-1 (-9)), (3 7), (2 11), -2] =
[-10, 10, 13, -2] =>
[(-10 (-2)), (10 13)] =
[-12, 23]
Constraints:
-101 < arr[i] < 101
You may assume that each arr[i] is unique
Here's my attempt at solving this problem:
def sumFirstAndLast (array):
if len(array) == 2:
return array
else:
left = 0
right = len(array) - 1
result = []
while left < right:
result.append(array[left] array[right])
left = 1
right -= 1
array = result
result = sumFirstAndLast(array)
return result
But it's throwing an error:
Traceback (most recent call last):
File "<string>", line 22, in <module>
File "<string>", line 11, in sumFirstAndLast
IndexError: list index out of range
>
Can someone provide me with a solution to this problem? Why am I getting this error? Is my logic to approaching this problem incorrect?
CodePudding user response：
array = resultandresult = sumFirstAndLast(array)should be put outside thewhileloopleftcould be equal torightif there are odd elements. Afterwhile left < rightwe need an additional condition checkif left == right.
The code can be as follows:
def sumFirstAndLast (array):
if len(array) == 2:
return array
else:
left = 0
right = len(array) - 1
result = []
while left < right:
result.append(array[left] array[right])
left = 1
right -= 1
if left == right:
result.append(array[left])
return sumFirstAndLast(result)
CodePudding user response：
I think recursion makes it harder to reason about what's going on (and thus, it's harder to reason about what's going wrong).
I would instead solve this iteratively, repeatedly performing the operation until you have a list with only two elements. The code ends up being pretty similar to the recursive version, but in my opinion it's much more readable (and thus much easier to debug):
def sumFirstAndLast (array):
if len(array) == 2:
return array
result = array.copy()
while len(result) > 2:
left = 0
right = len(result) - 1
new_result = []
while left < right:
new_result.append(result[left] result[right])
left = 1
right -= 1
if left == right:
new_result.append(result[left])
result = new_result
return result
CodePudding user response：
Some issues:
The indentation of two statements is wrong. The recursive call should not be made within the loop, but once the loop has been completed.
When the size of the array is odd, then the middle element is currently ignored and drops out. It should still be added to the result.
Not a huge problem if it is guaranteed, but you should better guard your function for the case the array has fewer than 2 values.
So without changing anything else to your code, it would become:
def sumFirstAndLast (array):
if len(array) <= 2:
return array
else:
left = 0
right = len(array) - 1
result = []
while left < right:
result.append(array[left] array[right])
left = 1
right -= 1
if left == right: # There is a middle element. It needs to be retained
result.append(array[left])
array = result
result = sumFirstAndLast(array) # recursion outside of the loop
return result
In a more compact, iterative version, it could be:
def sumFirstAndLast (array):
while len(array) > 2:
array = [
array[i] array[-i-1] for i in range(len(array) // 2)
] ([array[len(array) // 2]] if len(array) % 2 else [])
return array
CodePudding user response：
I'm gonna try to give you some tips as well.
Basically when you are solving a problem, you should break it into smaller problems. Start for the input. As you are working with operations 2 to 2, you should think, well what will happen if the input is minor than 2, that is the minimun required number for you to operate. Second, what happens if my input is odd or even? is it the same? In this case not. Lastly, try to approach a single loop and see the output before looping the whole thing and get a messy output.
With that in mind, you will solve the problem if the provided input doesn't have a minimun required size for operation:
if len(array) < 2:
return "Array must be of size bigger than 2"
Solve a single loop for odd cases:
for i in range(int(len(array) / 2) len(array) % 2):
if i < len(array) - i - 1:
new_array.append(array[i] array[len(array) - i - 1])
Solve a single loop for even cases:
for i in range(int(len(array) / 2) len(array) % 2):
if i < len(array) - i - 1:
new_array.append(array[i] array[len(array) - i - 1])
if len(array) % 2:
new_array.append(array[int(len(array) / 2)])
Now you have a single case loop, do the complete loop:
while len(array) > 2:
for i in range(int(len(array) / 2) len(array) % 2):
if i < len(array) - i - 1:
new_array.append(array[i] array[len(array) - i - 1])
if len(array) % 2:
new_array.append(array[int(len(array) / 2)])
array = new_array
new_array = []
Join all of that together and you have your Solution:
def solve(array):
if len(array) < 2:
return "Array must be of size bigger than 2"
new_array = []
while len(array) > 2:
for i in range(int(len(array) / 2) len(array) % 2):
if i < len(array) - i - 1:
new_array.append(array[i] array[len(array) - i - 1])
if len(array) % 2:
new_array.append(array[int(len(array) / 2)])
array = new_array
new_array = []
return array
At the end you can search for a compact solution, because now you at least solved the question in the interview, and got the logic.
def solve(array):
if len(array) < 2:
return "Array must be of size bigger than 2"
while len(array) > 2:
remainder = (array[int(len(array) / 2)]) if len(array) % 2 else False
array = [(array[i] array[len(array) - i - 1]) for i in range(int(len(array) / 2))]
array.append(remainder) if remainder is not False else None
return array