Sherlock and Array
Hello World!
Let’s get going with the problem Sherlock and Array on HackerRank. You may click on the title to read the problem statement. So let’s start…
The problem states that we have been given a list A of length n, and we need to find an index i such that the sum of the elements of its left is equal to the sum of the elements on its right. We need to print “YES” if such an i exists, else we need to print “NO”.
Let’s try the trivial approach, we can iterate from index i+1 to n-2 and can split the list into two temporary lists and find the sum of those two lists and compare if they match or not. This is a fairly straightforward approach and it is sure that it works. We can still come up with a better solution. Let me guide you through it.
Consider a weighing balance.
Let i = 0 and j = n-1. Now, put an element at i index in left balance and j index in right balance. If the left balance is heavier(i.e. the sum is greater), decrement j and add jth element in right balance. As soon as right balance becomes heavier, decrement i and add ith element in left balance. Do this till i != j. Once i becomes equal to j, you can check if left balance is equal to right balance or not.
Another way which I’ll discuss will make use of only one variable to track the equality and is more efficient. Initialize a variable ans = 0, i = 0 and j = n-1. Now, if ans ≥ 0, subtract jth element from ans and decrement j. Else, add ith element to ans and increment i. Run the loop till i != j. Once i becomes equal to j, check if ans is still equal to zero or not. If yes, print “YES”, else “NO”.
Open for suggestions. The code for this problem in Python3 can be found here.
Happy coding…
