Good Arrays

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
12 upvotes
Asked in companies
AdobeOlaCapegemini Consulting India Private Limited

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

2
5
1 2 4 3 6
3
1 1 1

Sample Output 1 :

1
3

Explanation Of Sample Input 1:

In test case 1:
We have A = [1 2 4 3 6]
If we delete A[0], we will have B= [2 4 3 6], B[0] + B[2] != B[1] + B[3] 
If we delete A[1], we will have B= [1 4 3 6], B[0] + B[2] != B[1] + B[3] 
If we delete A[2], we will have B= [1 2 3 6], B[0] + B[2] != B[1] + B[3] 
If we delete A[3], we will have B= [1 2 4 6], B[0] + B[2] != B[1] + B[3]
If we delete A[3], we will have B= [1 2 4 3], B[0] + B[2]  = B[1] + B[3]

Only 1 good array can be formed.

In test case 2:
We have A = [1 1 1]
If we delete A[0], we will have B= [1 1], B[0] = B[1]
If we delete A[1], we will have B= [1 1], B[0] = B[1]
If we delete A[2], we will have B= [1 1], B[0] = B[1]

3 good arrays can be formed.

Sample Input 2 :

2
9
2 2 1 1 1 2 1 1 2 
7
2 1 2 2 1 1 1

Sample Output 2 :

3
1
Hint

Delete all index values one by one and make a new array after deleting

Approaches (2)
Brute Force

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.
Time Complexity

O( N^2 ),  where N is the length of the array
 

There are N indexes in array ‘A’, and for each index, we iterate over a new Array of length N-1, thus time complexity is O( N^2 ).

Space Complexity

O(N^2),  where N is the length of the array

 

There are N indexes in array ‘A’, and for each index, we are creating a new array ‘B’ of length N-1, thus time complexity is O( N^2 ).

Code Solution
(100% EXP penalty)
Good Arrays
Full screen
Console