Good Arrays
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

Question

Good Arrays

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

Accepted Answer

Algorithm :

1) Create a variable ‘res’ =0, which will store the number of good arrays that can be formed.
2) Create four variables ‘oddRightSum’ = 0, ‘evenRightSum’ = 0, ‘oddLeftSum’ = 0, ‘evenLeftSum’ = 0;
3) Iterate over all index ‘i’ in array ‘A:
3.1) If ‘i’ is even, then add the current element to ‘evenRightSum’
3.2) If ‘i’ is odd, then add the current element to ‘oddRightSum’
4) Iterate over all index ‘i’ in array ‘A:
4.1) If ‘i’ is odd, then decrease ‘oddRightSum’ by the current element.
4.2) If ‘i’ is even, then decrease ‘evenRightSum’ by the current element.
4.3) If ‘leftEvenSum’ + ’rightOddSum’ == ‘leftOddSum’ + ‘rightEvenSum’., then increment ‘res’, as we
have found one good array.
4.4) If ‘i’ is odd, then increase ‘oddRightSum’ by the current element.
4.5) If ‘i’ is even, then increase ‘evenRightSum’ by the current element.
5) Return ‘res’ variable.

TC : O( N ), where N=size of the array
SC : O(1)

Accepted Answer

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.

Space Complexity: O(n^2)Explanation:

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 ).

Time Complexity: O(n^2)Explanation:

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 ).

Java (SE 1.8)

/*

    Time Complexity: O(N^2)

    Space Complexity: O(N^2)



    Where N is length of the array

*/



import java.util.ArrayList;



public class Solution 

{

    public static int goodArrays(ArrayList a, int n) 

    {   

		// Create a variable 'res' which will store the number of good arrays that can be formed

        int res = 0;

        

		// Iterate over all index 'i' in array 'A'

	    for (int i = 0; i < n; i++) 

        {   

			// Create a new array 'B' which contain all elements of array 'A' except the one at index 'i'

		    ArrayList b = new ArrayList<>();



		    for (int j = 0; j < n; j++) 

            {

			    if ( i != j ) 

                {

				   b.add(a.get(j));

			    }

		    }

            

			// Create two variables 'evenSum' and 'oddSum' which will store sums of elements in even and odd index of the array 'B'

		    int evenSum = 0, oddSum = 0;

            

			// Iterate over all the index 'j' in array B

            // If jth index is odd, then add the current element in the 'oddSum' variable

            // If jth index is even, then add the current element in the 'evenSum' variable

		    for (int j = 0; j < n - 1; j++) 

            {

			    if ( j % 2 == 0 ) 

                {

				   evenSum += b.get(j);

			    } 

                else 

                {

				   oddSum += b.get(j);

			    }

		    }

            

			// If 'oddSum' == 'evenSum' then increment 'res' as we have found one good array

		    if ( evenSum == oddSum ) 

            {

			    res++;

		    }

	    }



	    return res;

    }

}

C++ (g++ 5.4)

/*

    Time Complexity: O(N^2)

    Space Complexity: O(N^2)



    Where N is length of the array

*/



int goodArrays(vector &a, int n) 

{   

    // Create a variable 'res' which will store the number of good arrays that can be formed

	int res = 0;

    

    // Iterate over all index 'i' in array 'A'

	for (int i = 0; i < n; i++) 

    {   

        // Create a new array 'B' which contain all elements of array 'A' except the one at index 'i'

		vector b;



		for (int j = 0; j < n; j++) 

        {

			if ( i != j ) 

            {

				b.push_back(a[j]);

			}

		}

        

        // Create two variables 'evenSum' and 'oddSum' which will store sums of elements in even and odd index of the array 'B'

		int evenSum = 0, oddSum = 0;

        

        // Iterate over all the index 'j' in array B

        // If jth index is odd, then add the current element in the 'oddSum' variable

        // If jth index is even, then add the current element in the 'evenSum' variable

		for (int j = 0; j < n - 1; j++) 

        {

			if ( j % 2 == 0 ) 

            {

				evenSum += b[j];

			} 

            else 

            {

				oddSum += b[j];

			}

		}

        

        // If 'oddSum' == 'evenSum' then increment 'res' as we have found one good array

		if ( evenSum == oddSum ) 

        {

			res++;

		}

	}



	return res;

}

Python (3.5)

"""

    Time Complexity: O(N^2)

    Space Complexity: O(N^2)



    Where N is length of the array

"""



def goodArrays(a, n):



    #Create a variable 'res' which will store the number of good arrays that can be formed

    res = 0

    

    # Iterate over all index 'i' in array 'A'

    for i in range(n):



        # Create a new array 'B' which contain all elements of array 'A' except the one at index 'i'

        b = []



        for j in range(n):

            if (i != j):

                b.append(a[j])

        

        # Create two variables 'evenSum' and 'oddSum' which will store sums of elements in even and odd index of the array 'B'

        evenSum = 0

        oddSum = 0

        

        # Iterate over all the index 'j' in array B

        # If jth index is odd, then add the current element in the 'oddSum' variable

        # If jth index is even, then add the current element in the 'evenSum' variable

        for j in range(n-1):

            if (j % 2 == 0):

                evenSum += b[j]

            else:

                oddSum += b[j]

        

        # If 'oddSum' == 'evenSum' then increment 'res' as we have found one good array

        if (evenSum == oddSum):

            res += 1



    return res

Accepted Answer

Efficient

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.

Space Complexity: O(1)Explanation:

O(1)

Constant Space is used.

Time Complexity: O(n)Explanation:

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

We are only iterating over the array ‘A’ of length N, thus complexity is O( N ).

Java (SE 1.8)

/*

    Time Complexity: O(N)

    Space Complexity: O(1)



    Where N is length of the array

*/



import java.util.ArrayList;



public class Solution 

{

    public static int goodArrays(ArrayList a, int n) 

    {   

        // Create a variable 'res' which will store the number of good arrays that can be formed

        int res = 0;

        

        // Create four variables 'oddRightSum' 'evenRightSum' 'oddLeftSum' 'evenLeftSum'

        int leftEvenSum = 0, rightOddSum = 0, leftOddSum = 0, rightEvenSum = 0;

        

        // Iterate over all index 'i' in array A

        // If ith index is even, then add the current element to 'evenRightSum'

        // If ith index is odd, then add the current element to 'oddRightSum'

        for (int i = 0; i < n; i++) 

        {

            if (i % 2 == 0) 

            {

                rightEvenSum += a.get(i);

            } 

            else 

            {

                rightOddSum += a.get(i);

            }

        }

        

        // Iterate over array A

        for (int i = 0; i < n; i++) 

        {   

            // 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

            if (i % 2 == 0) 

            {

                rightEvenSum -= a.get(i);

            } 

            else 

            {

                rightOddSum -= a.get(i);

            }



            if (leftEvenSum + rightOddSum == leftOddSum + rightEvenSum) 

            {

                res++;

            }



            if (i % 2 == 0) 

            {

                leftEvenSum += a.get(i);

            } 

            else 

            {

                leftOddSum += a.get(i);

            }

        }

        return res;

    }

}

C++ (g++ 5.4)

/*

    Time Complexity: O(N)

    Space Complexity: O(1)



    Where N is length of the array

*/



int goodArrays(vector &a, int n) 

{   

    // Create a variable 'res' which will store the number of good arrays that can be formed

	int res = 0;

    

    // Create a variable 'res' which will store the number of good arrays that can be formed

	int leftEvenSum = 0, rightOddSum = 0, leftOddSum = 0, rightEvenSum = 0;

    

    // Iterate over all index 'i' in array A

    // If ith index is even, then add the current element to 'evenRightSum'

    // If ith index is odd, then add the current element to 'oddRightSum' 

	for (int i = 0; i < n; i++) 

    {

		if ( i % 2 == 0 ) 

        {

			rightEvenSum += a[i];

		} 

        else 

        {

			rightOddSum += a[i];

		}

	}

    

    // Iterate over array A

	for (int i = 0; i < n; i++) 

    {   

        // 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

		if ( i % 2 == 0) 

        {

			rightEvenSum -= a[i];

		} 

        else 

        {

			rightOddSum -= a[i];

		}



		if ( leftEvenSum + rightOddSum == leftOddSum + rightEvenSum ) 

        {

			res++;

		}



		if ( i % 2 == 0) 

        {

			leftEvenSum += a[i];

		} 

        else 

        {

			leftOddSum += a[i];

		}

	}

	return res;

}

Python (3.5)

"""

    Time Complexity: O(N)

    Space Complexity: O(1)



    Where N is length of the array

"""



def goodArrays(a, n) :



    # Create a variable 'res' which will store the number of good arrays that can be formed

	res = 0

    

    # Create a variable 'res' which will store the number of good arrays that can be formed

	leftEvenSum = 0

	rightOddSum = 0

	leftOddSum = 0

	rightEvenSum = 0

    

    # Iterate over all index 'i' in array A

    # If ith index is even, then add the current element to 'evenRightSum'

    # If ith index is odd, then add the current element to 'oddRightSum' 

	for i in range(n):

		if ( i % 2 == 0 ) :

			rightEvenSum += a[i]

		else :

			rightOddSum += a[i]

		

	

    # Iterate over array A

	for i in range(n):

        

        # 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

		if ( i % 2 == 0): 

			rightEvenSum -= a[i]

		else :

			rightOddSum -= a[i]

		



		if ( leftEvenSum + rightOddSum == leftOddSum + rightEvenSum ) :

			res+=1

		



		if ( i % 2 == 0): 

			leftEvenSum += a[i]

		else :

			leftOddSum += a[i]

		



	



	return res

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 :

For Example :

Input Format :

Output Format :

Note :

Constraints :

Top Adobe Member Technical Staff interview questions & answers

Popular interview questions of Member Technical Staff

Top HR questions asked in Adobe Member Technical Staff