Last Updated: 10 Apr, 2021
Good Arrays
Moderate
Asked in companies
You are given an array ‘A’ of length ‘N’, you have to choose an element from any index in this array and delete it. After deleting the element you will get a new array of length ‘N’-1. Your task is to find the number of such arrays of length ‘N’-1 which are good.
Note :
An array is called good if the sum of elements in odd indexes is equal to the sum of elements in even indexes.
For Example :
In array A= [1 2 4 3 6], if we delete A[4]=6, we will get new array B= [1 2 4 3], where B[0] + B[2] = B[1] + B[3] = 5, which means array B is good.
Input Format :
The first line of the input contains ‘T’ denoting the number of test cases.
The first line of each test case contains the three integers N, length of the array.
The second line of each test case contains N space-separated integers of the array A.
Output Format :
For each test case, print an integer denoting the number of good arrays that can be formed.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function
Constraints :
1 <= T <= 5
1 <= N <= 3000
-5000 <= A[i] <= 5000
Where 'A[i]' denotes the 'ith' element of the given array.
Time Limit: 1sec
Approaches
Explanation:
In this approach, we will delete all index values one by one and make a new array after deleting. Then in the new array, we just check the sum of elements in even and odd index and compare them.
Algorithm:
- Create a variable ‘res’ =0, which will store the number of good arrays that can be formed.
- Iterate over all index ‘i’ in array ‘A:
- Create a new array ‘B’ which contain all elements of array ‘A’, except the one at index ‘i’
- Create two variables ‘evenSum’= 0 and ‘oddSum’= 0, which will store sums of elements in even and odd index of the array ‘B’
- Iterate over all the index ‘j’ in array B:
- If ‘j’ (the index in array B) is odd, then add the current element in the ‘oddSum’ variable.
- If ‘j’ is even, then add the current element in the ’evenSum’ variable.
- If ‘oddSum’ == ‘evenSum’, then increment ‘res’, as we have found one good array.
- Return ‘res’ variable.
Explanation:
- If for each index ‘i’ we somehow knew what is the sum of the even index element in the left part (i.e. even index in 0…’i’-1) and what is the sum of the odd index element in the right part (i.e. odd index in i+1… ’N’-1), then from the two we can find the sum of even index elements in the array ‘B’ which we get after deleting index ‘i’.
- Eg: if A= [0, 1, 2 ,3, 4], and ‘i’= 2, then ‘leftEvenSum’ = A[0], and ‘rightOddSum’= A[3]. Then after deleting index ‘i’ element we will get B= [0, 1, 3, 4], where sum of even index element is B[0] + B[2] = A[1] + A[3] = ‘leftEvenSum’ + ’rightOddSum’
- Similarly to get the sum of odd index sum in array ‘B’, we can find ‘leftOddSum’ and ‘rightEvenSum’.
- In conclusion, for the array ‘B’ to be good, ‘even index element sum’ == ‘odd index element sum’ or simply,
‘leftEvenSum’ + ’rightOddSum’ == ‘leftOddSum’ + ‘rightEvenSum’.
- If we move from index ‘i’-1 to ‘i’, then we will all 4 variables accordingly.
- If ‘i’ is odd, then decrease ‘oddRightSum’ by the current element, else we decrease ‘evenRightSum’ by the current element. This is because we are deleting the current element which previously ( from index ‘i’-1 ) was a part of the right part of the array.
- After moving from index ‘i’ to ‘i’+1, the current element will become part of the left part of the array, therefore we will add it to the ‘leftOddSum’ or ‘leftEvenSum’ according to the parity of ‘i’.
Algorithm:
- Create a variable ‘res’ =0, which will store the number of good arrays that can be formed.
- Create four variables ‘oddRightSum’ = 0, ‘evenRightSum’ = 0, ‘oddLeftSum’ = 0, ‘evenLeftSum’ = 0;
- Iterate over all index ‘i’ in array ‘A:
- If ‘i’ is even, then add the current element to ‘evenRightSum’
- If ‘i’ is odd, then add the current element to ‘oddRightSum’
- Iterate over all index ‘i’ in array ‘A:
- If ‘i’ is odd, then decrease ‘oddRightSum’ by the current element.
- If ‘i’ is even, then decrease ‘evenRightSum’ by the current element.
- If ‘leftEvenSum’ + ’rightOddSum’ == ‘leftOddSum’ + ‘rightEvenSum’., then increment ‘res’, as we have found one good array.
- If ‘i’ is odd, then increase ‘oddRightSum’ by the current element.
- If ‘i’ is even, then increase ‘evenRightSum’ by the current element.
- Return ‘res’ variable.