Make All Elements Equal by Subtracting Power of 2
Given an array A[] of length N, the task is to check if it is possible to make all elements equal using a given operation any number of times (including zero). Choose two distinct indices let’s say i and j, where (i != j), then subtract a power of two from Ai let’s say 2X, where X must be greater than or equal to 1. After that add that subtracted value in Aj.
Examples:
Input: N = 3, A[] = {4, 8, 24}
Output: YES
Explanation: The operations took place as:
- First Operation: Choose i = 3 and j = 1, then subtract 23 = 8 from A3 and add it into A1. Then updated A[] = {12, 8, 16}
- Second Operation: Choose i = 3 and j = 2, then subtract 22 = 4 from A3 and add it into A2. Then updated A[] = {12, 12, 12}
Now, it can be verified that all the elements become equal. Thus output is YES.
Input: N = 3, A[] = {5, 8, 2}
Output: NO
Explanation: It can be verified that all the elements can’t make equal using given operation.
Approach: To solve the problem follow the below observations:
Observations:
The problem is observation based. There are some observations which are:
- Possibility of making all elements equal: It must be noted that all the elements can be made only equal if and only if they can be distributed equally. Formally, If each element can be converted into average using given operation then it is possible to make them all equal. This can be confirmed by checking that, If Sum of element is perfectly divisible by count of elements then it is possible to make them all equal.
- Subtraction and addition operation: It must be noted that in given operation, we can subtract 2X from an element and adding it into other element. Here constraint is given that X must be >= 1. It gives that the subtracted value will always in the power of two as well as even and >=2. So, we can check the parity of difference between current element and average iterating over A[]. It can be verified that, each difference, which is even can be achieve using given operation. While odd difference can’t be achieved.
Steps were taken to solve the problem:
- Create a variable let say Sum and calculate the sum iterating over A[].
- If (Sum % N != 0)
- Then output NO.
- Else
- Declare a variable let say Avg and initialize it equal to Sum/N
- Declare a boolean variable let say Flag
- Run a loop for each element of A[] and follow below mentioned steps under the scope of loop:
- Difference = Absolute(Current_element – Avg)
- If (Difference % 2 != 0)
- Flag = False
- Break
- If (Flag == True)
- Output YES
- Else
- Output NO
Below is the code to implement above approach:
C++
#include <iostream> #include <vector> using namespace std; // Function to check if it is possible to make all elements equal void Is_Possible( int N, vector< long long >& A) { // Variable to store the sum of all elements long long sum = 0; // Loop for calculating the sum for ( int i = 0; i < N; i++) { sum += A[i]; } // Checking for the possibility that all elements can be made equal or not if (sum % N != 0) { cout << "No" << endl; } // Else will execute if elements can be made equal else { // Variable storing the average of all elements long long avg = sum / N; // Boolean flag for storing the answer bool flag = true ; // Checking the difference of each element of A[] with avg. for ( long long x : A) { long long diff = abs (x - avg); if (diff % 2 != 0) { flag = false ; break ; } } // If all differences are even, then the answer is YES; otherwise, it is NO cout << (flag ? "YES" : "NO" ) << endl; } } // Driver Function int main() { // Inputs int N = 3; vector< long long > A = {4, 8, 24}; // Function call Is_Possible(N, A); return 0; } |
Java
// Java code to implement the approach import java.util.*; // Driver Class class GFG { // Driver Function public static void main(String[] args) { // Inputs int N = 3 ; long [] A = { 4 , 8 , 24 }; // Function call Is_Possible(N, A); } public static void Is_Possible( int N, long [] A) { // Variable to store the sum of // all elements long sum = 0 ; // Loop for calcultaing sum for ( int i = 0 ; i < N; i++) { sum += A[i]; } // Checking for possibility that // all elements can be make equal or not if (sum % N != 0 ) { System.out.println("No"); } // Else will execute, If can be // make equal else { // variable which is storing avg. // of all elements long avg = sum / N; // Boolean flag for storing ans boolean flag = true ; // Checking the diffference of each // element of A[] With avg. for ( long x : A) { long diff = Math.abs(x - avg); if (diff % 2 != 0 ) { flag = false ; break ; } } // If all differences are even then // ans will YES else NO System.out.println(flag ? "YES" : "NO"); } } } |
Python3
# Function to check if it is possible to make all elements equal def is_possible(N, A): # Variable to store the sum of all elements _sum = sum (A) # Checking for the possibility that all elements can be made equal or not if _sum % N ! = 0 : print ( "No" ) else : # Variable storing the average of all elements avg = _sum / / N # Boolean flag for storing the answer flag = True # Checking the difference of each element of A[] with avg. for x in A: diff = abs (x - avg) if diff % 2 ! = 0 : flag = False break # If all differences are even, then the answer is YES; otherwise, it is NO print ( "YES" if flag else "NO" ) # Driver Function if __name__ = = "__main__" : # Inputs N = 3 A = [ 4 , 8 , 24 ] # Function call is_possible(N, A) |
C#
using System; class GFG { // Driver Function public static void Main( string [] args) { // Inputs int N = 3; long [] A = { 4, 8, 24 }; // Function call IsPossible(N, A); } public static void IsPossible( int N, long [] A) { // Variable to store the sum of all elements long sum = 0; // Loop for calculating sum for ( int i = 0; i < N; i++) { sum += A[i]; } // Checking for the possibility that all elements // can be made equal or not if (sum % N != 0) { Console.WriteLine( "No" ); } // Else will execute, If can be made equal else { // Variable which is storing avg. of all // elements long avg = sum / N; // Boolean flag for storing ans bool flag = true ; // Checking the difference of each element of // A[] With avg. foreach ( long x in A) { long diff = Math.Abs(x - avg); if (diff % 2 != 0) { flag = false ; break ; } } // If all differences are even then ans will be // YES else NO Console.WriteLine(flag ? "YES" : "NO" ); } } } |
Javascript
// JavaScript Implementation of the given problem // Function to check if it is possible to make // all elements of array 'A' equal function isPossible(N, A) { // Variable to store the sum of all elements let sum = 0; // Loop for calculating sum for (let i = 0; i < N; i++) { sum += A[i]; } // Checking for the possibility that all // elements can be made equal or not if (sum % N !== 0) { console.log( "No" ); } else { // Variable which is storing average // of all elements let avg = sum / N; // Boolean flag for storing the answer let flag = true ; // Checking the difference of each // element of A[] with avg. for (let i = 0; i < N; i++) { let diff = Math.abs(A[i] - avg); if (diff % 2 !== 0) { flag = false ; break ; } } // If all differences are even // then print YES else NO console.log(flag ? "YES" : "NO" ); } } // Inputs const N = 3; const A = [4, 8, 24]; // Function call isPossible(N, A); |
YES
Time Complexity: O(N)
Auxiliary space: O(1)