Minimum Operations To Make Array Equal
You are given an array ‘ARR’ of length ‘N’ which is filled with the values such that ARR[i] = (2*i + 1). You have to perform operations on the ‘ARR’ to make all elements of the array equal. In one operation, you can choose two elements from the array ‘ARR’ say ‘i’ and ‘j’, and can increment the value of ‘ARR[i]’ by one and decrement the value of ‘ARR[j]’ by one.

You have to find the minimum number of operations to make all the elements of the array ‘ARR’ equal. It is guaranteed that all elements of the array can be made equal using some operations.

Input format:

The first line of input contains an integer ‘T’, denoting the number of test cases. The first line of each test case contains an integer ‘N’, denoting the length of the array.

Output format:

For each test case, print the minimum number of operations to make all the elements of the array equal. Output for each test case is printed on a separate line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1

Question

Minimum Operations To Make Array Equal

You are given an array ‘ARR’ of length ‘N’ which is filled with the values such that ARR[i] = (2*i + 1). You have to perform operations on the ‘ARR’ to make all elements of the array equal. In one operation, you can choose two elements from the array ‘ARR’ say ‘i’ and ‘j’, and can increment the value of ‘ARR[i]’ by one and decrement the value of ‘ARR[j]’ by one.

You have to find the minimum number of operations to make all the elements of the array ‘ARR’ equal. It is guaranteed that all elements of the array can be made equal using some operations.

Input format:

The first line of input contains an integer ‘T’, denoting the number of test cases. 

The first line of each test case contains an integer ‘N’, denoting the length of the array.

Output format:

For each test case, print the minimum number of operations to make all the elements of the array equal.

Output for each test case is printed on a separate line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 1000
1 <= N <= 10^9

Time Limit: 1 sec

Follow Up:

Can you do this in constant time and space?

Accepted Answer

Brute Force

The idea behind this approach is we have to calculate the average of all the elements of the array ‘ARR’ because the sum of all elements of the array always remains constant.
So calculating the average will help us to virtually divide the elements into two halves around the average i.e left and the right. So calculating the answer for the left half only will be our required answer. It is because in one operation we will choose one element from the left half and one element from the right half and therefore performing operation only left will give us the answer. We will choose the elements which are at equal distance from their average i.e (0 and N-1) or (1 and N-2) etc. therefore if the 0'th element requires ‘K’ operations to become equal to average then the (N-1)'th element will also require ‘K’ operations to become equal to the average and this whole operation to convert 0'th element and the (N-1)'th element will be considered as one single operation.

Algorithm:

Construct an array ARR of size N such that ARR[i] = (2*i + 1) where 0 <= i < N.
Now create a variable Sum initialized to 0 and while constructing the above array add all the elements and store the result in Sum.
Now create a variable Avg which denotes the average of all array elements. Set Avg as Sum / N.
Create a variable minOperations initialized to 0.
Since we have to traverse over only on the left half of the array ARR, So we will traverse over the array ARR till N/2 and for each element find the cost to make it equal to the average i.e (Avg - ARR[i]]) and add this cost to the variable minOperations.
Finally, return the minOperations which is our required answer.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the length of the array.

Since we are constructing an array ARR, which takes O(N) space. So, overall space complexity will be O(N).

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the length of the array.

Constructing the array ARR will take O(N) time. And then traversing over half of the array will also takes O(N) time. Therefore, the overall time complexity will be O(N).

Java (SE 1.8)

/*

   Time Complexity: O(N)

   Space Complexity: O(N)



   Where 'N' is the length of the array

*/



public class Solution 

{

	public static long makeArrayEqual(int n) 

    {

		// Create an array arr of length N to construct it according to the problem statement

		int[] arr = new int[n];



		// Create a variable sum to calculate the sum of all array elements

		long sum = 0;



		// Construct the array and also calculate the sum of array elements

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

        {

			arr[i] = 2 * i + 1;

			sum += arr[i];

		}



		// Create a variable avg to store the average of the array

		long avg = sum / n;



		// Create a variable minOperations to store the operations required to make all array elements equal

		long minOperations = 0;



		// Traverse over left part of the array

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

        {

			minOperations += (avg - arr[i]);

		}



		return minOperations;

	}

}

Python (3.5)

'''

   Time Complexity: O(N)

   Space Complexity: O(N)



   Where 'N' is the length of the array

'''



def makeArrayEqual(n):



    # Create an array arr of length N to construct it according to the problem statement

    arr = [0 for j in range(n)]



    # Create a variable sum to calculate the sum of all array elements

    sum = 0



    # Construct the array and also calculate the sum of array elements

    for i in range(n):



        arr[i] = 2 * i + 1

        sum += arr[i]



    # Create a variable avg to store the average of the array

    avg = sum // n



    # Create a variable minOperations to store the operations required to make all array elements equal

    minOperations = 0



    # Traverse over left part of the array

    for i in range(n // 2):

        minOperations += (avg - arr[i])



    return minOperations

C++ (g++ 5.4)

/*

   Time Complexity: O(N)

   Space Complexity: O(N)



   Where 'N' is the length of the array

*/



long long int makeArrayEqual(int n)

{

	// Create an array arr of length N to construct it according to the problem statement

	vector arr(n , 0);



	// Create a variable sum to calculate the sum of all array elements

	long long int sum = 0;



	// Construct the array and also calculate the sum of array elements

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

	{

		arr[i] = 2 * i + 1;

		sum += arr[i];

	}



	// Create a variable avg to store the average of the array

	long long int avg = sum / n;



	// Create a variable minOperations to store the operations required to make all array elements equal

	long long int minOperations = 0;



	// Traverse over left part of the array

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

	{

		minOperations += (avg - arr[i]);

	}



	return minOperations;

}

Accepted Answer

Using Cases

It is the optimized version from the previous approach.
In this approach, we have to consider two cases, i.e, if the length of the array is even or odd.
If the length of the array is even then the answer will be the sum of all the odd numbers on the left of the average of the array i.e (1 + 3 + 5 …. ) that will be equal to N^2 but since we are considering only left half (containing N/2 elements) therefore it will be equal to N^2/4.
If the length of the array is odd then the answer will be the sum of all the even numbers on the left of the average of the array i.e (2 + 4 + 6 …. ) that will be equal to N*(N+1) but since we are considering only left half therefore it will be equal to (N/2)*(N/2 + 1).
For example, If N = 5 then ARR = {1, 3, 5, 7, 9} so the average will be 5 and we will try to convert each element into 5. So considering only left half of the array i.e {1, 3} and to convert them to 5 will require {4, 2} cost respectively. So the cost will the sum of the first N/2 even numbers.
For example, If N = 6 then ARR = {1, 3, 5, 7, 9, 11} so the average will be 6 and we will try to convert each element into 6. So considering only left half of the array i.e {1, 3, 5} and to convert them to 6 will require {5, 3, 1} cost respectively. So the cost will be the sum of the first N/2 odd numbers.

Algorithm:

Create a variable Mid which is equal to N/2.
If N is even, then we will return Mid * Mid.
Otherwise, we will return Mid*(Mid + 1).

Space Complexity: O(1)Explanation:

O(1)

Since constant space is being used. So overall space complexity will be O(1).

Time Complexity: O(1)Explanation: