O(n) time complexity and O(1) space Complexity solution in Python


#1

This problem can solved in 0(n) time complexity with out using any extra memory space.
Step 1: Compute all even index elements sum and also odd index elements sum as suffix sums. Set Prefix even and Odd sum to 0
Step 2: Iterate array and subtract the value of A[i] from suffix sums depending on even or odd. Odd and even position of elements will be changed after the current index. Check if prefix (odd /even) + suffix (even/odd) == prefix (even/odd) + suffix(odd/even). If yes, A[i] is one of the possibilities