Given array A[] of size N and integer X, the task is to find the minimum number of operations to make any two elements equal in the array. In one operation choose any element A[i] and replace it with A[i] & X. where & is bitwise AND. If such operations do not exist print -1.
Examples:
Input: A[] = {1, 2, 3, 7}, X = 3
Output: 1
Explanation: Performing above operation on A[4] = 7, A[4] = A[4] & X = 7 & 3 = 3. Array A[] becomes {1, 2, 3, 3}, 3 exists on 3rd position so in one operation two elements can be made equal in array A[].Input: A[] = {1, 2, 3}, X = 7
Output: -1
Explanation: It is not possible to make any two elements equal by performing above operations any number of times.
Naive approach: The basic way to solve the problem is as follows:
Making bitwise AND of current element and checking whether if any other element exists with same value.
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized based on the following idea:
This problem can be divided in four cases:
- Case 1: Two equal elements already exist in array A[], In that case answer will be 0.
- Case 2: It is not possible to create two elements which are equal by above operations, In that case answer will be -1.
- Case 3: It is possible to make any two elements equal by performing above operations exactly once.
- Case 4: It is possible to make any two elements equal by performing above operations exactly twice.
Follow the steps below to solve the problem:
- Creating HashMap[].
- Iterating from 1 to N and filling frequency HashMap[] if some element repeats again return 0.
- Iterating from 1 to N and for each iteration remove the current element from HashMap[] and perform an operation on the current index and check whether it exists in HashMap[] if it exists return 1 else insert the current element again in HashMap[].
- Clear the HashMap[].
- Iterating from 1 to N and performing an operation on each element along with filling HashMap[], if the frequency of any element is more than 2 then return 2.
- Finally, if the function reaches the end return -1.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to minimum operations required// to make two elements equal in array.int minOperations(int A[], int N, int M){ // Creating HashMap map<int, int> HashMap; for (int i = 0; i < N; i++) { // Filling frequency HashMap HashMap[A[i]]++; // If two values same already exist if (HashMap[A[i]] >= 2) return 0; } for (int i = 0; i < N; i++) { // Removing occurrence of current // element from HashMap HashMap[A[i]]--; // Performing operation on // current index int performOperation = A[i] & M; // Check if another element exists // with same value if (HashMap[performOperation]) return 1; // Inserting back occurrence // of element HashMap[A[i]]++; } // Clearing the HashMap HashMap.clear(); for (int i = 0; i < N; i++) { // Performing operation on // current index int performOperation = A[i] & M; // Inserting this element // in Hashmap HashMap[performOperation]++; // If two elements exist such that // both formed with operation if (HashMap[A[i]] == 2) return 2; } // If answer do not exist return -1;}// Driver Codeint main(){ // Input 1 int A[] = { 1, 2, 3, 7 }; int N = sizeof(A) / sizeof(A[0]); int X = 3; // Function Call cout << minOperations(A, N, X) << endl; // Input 2 int A1[] = { 1, 2, 3 }; int N1 = sizeof(A1) / sizeof(A1[0]); int X1 = 7; // Function Call cout << minOperations(A1, N1, X1) << endl; return 0;} |
Python3
# Python code to implement the approach# Function to minimum operations required# to make two elements equal in array.def minOperations(A, N, M): # Creating HashMap HashMap = {} for i in range(N): # If two values same already exist if A[i] in HashMap: return 0 # Filling frequency HashMap else: HashMap[A[i]] = 1 for i in range(N): # Removing occurrence of current # element from HashMap HashMap[A[i]] -= 1 # Performing operation on # current index performOperation = A[i] & M # Check if another element exists # with same value if (HashMap[performOperation]): return 1 # Inserting back occurrence # of element HashMap[A[i]] += 1 # Clearing the HashMap HashMap = {} for i in range(N): # Performing operation on # current index performOperation = A[i] & M # Inserting this element # in Hashmap if performOperation in HashMap: HashMap[performOperation] += 1 else: HashMap[performOperation] = 1 # If two elements exist such that # both formed with operation if (HashMap[A[i]] == 2): return 2 # If answer do not exist return -1 # Driver Code# Input 1A = [1, 2, 3, 7]N = len(A) X = 3# Function Callprint(minOperations(A, N, X))# Input 2A1 = [1, 2, 3]N1 = len(A1)X1 = 7# Function Callprint(minOperations(A1, N1, X1)) |
C#
//C# code to implement the approachusing System;using System.Collections.Generic;// Function to minimum operations required// to make two elements equal in array.class MainClass { public static int MinOperations(int[] A, int N, int M) { // Creating HashMap Dictionary<int, int> HashMap = new Dictionary<int, int>(); for (int i = 0; i < N; i++) { // Filling frequency HashMap if (HashMap.ContainsKey(A[i])) { HashMap[A[i]]++; } else { HashMap.Add(A[i], 1); } // If two values same already exist if (HashMap[A[i]] >= 2) { return 0; } } for (int i = 0; i < N; i++) { // Removing occurrence of current element from HashMap HashMap[A[i]]--; // Performing operation on current index int performOperation = A[i] & M; // Check if another element exists with same value if (HashMap.ContainsKey(performOperation) && HashMap[performOperation] > 0) { return 1; } // Inserting back occurrence of element HashMap[A[i]]++; } // Clearing the HashMap HashMap.Clear(); for (int i = 0; i < N; i++) { // Performing operation on current index int performOperation = A[i] & M; // Inserting this element in Hashmap if (HashMap.ContainsKey(performOperation)) { HashMap[performOperation]++; } else { HashMap.Add(performOperation, 1); } // If two elements exist such that both formed with operation if (HashMap[performOperation] == 2) { return 2; } } // If answer do not exist it will return -1 return -1; } // Drive Code public static void Main(string[] args) { // Input 1 int[] A = { 1, 2, 3, 7 }; int N = A.Length; int X = 3; // Test Case 1 Function Call Console.WriteLine(MinOperations(A, N, X)); // Input 2 int[] A1 = { 1, 2, 3 }; int N1 = A1.Length; int X1 = 7; // Test Case 2 Function Call Console.WriteLine(MinOperations(A1, N1, X1)); }}// This Code is contributed by nikhilsainiofficial546 |
Javascript
// JavaScript code to implement the approachfunction minOperations(A, N, M) { // Creating HashMap let HashMap = {}; for (let i = 0; i < N; i++) { // Filling frequency HashMap if (HashMap[A[i]] === undefined) HashMap[A[i]] = 0; HashMap[A[i]]++; // If two values same already exist if (HashMap[A[i]] >= 2) return 0; } for (let i = 0; i < N; i++) { // Removing occurrence of current // element from HashMap HashMap[A[i]]--; // Performing operation on // current index let performOperation = A[i] & M; // Check if another element exists // with same value if (HashMap[performOperation]) return 1; // Inserting back occurrence // of element HashMap[A[i]]++; } // Clearing the HashMap HashMap = {}; for (let i = 0; i < N; i++) { // Performing operation on // current index let performOperation = A[i] & M; // Inserting this element // in Hashmap if (HashMap[performOperation] === undefined) HashMap[performOperation] = 0; HashMap[performOperation]++; // If two elements exist such that // both formed with operation if (HashMap[A[i]] === 2) return 2; } // If answer do not exist return -1;}// Input 1let A = [1, 2, 3, 7];let N = A.length;let X = 3;// Function Callconsole.log(minOperations(A, N, X));// Input 2let A1 = [1, 2, 3];let N1 = A1.length;let X1 = 7;// Function Callconsole.log(minOperations(A1, N1, X1)); |
Java
/*package whatever //do not write package name here */import java.io.*;import java.util.*; class GFG { // Function to minimum operations required // to make two elements equal in array. static int minOperations(int A[], int N, int M) { // Creating HashMap Map<Integer, Integer> HashMap = new HashMap<Integer, Integer>(); for (int i = 0; i < N; i++) { // Filling frequency HashMap if (HashMap.containsKey(A[i])) HashMap.put(A[i], HashMap.get(A[i]) + 1); else HashMap.put(A[i], 1); // If two values same already exist if (HashMap.get(A[i]) >= 2) return 0; } for (int i = 0; i < N; i++) { // Removing occurrence of current // element from HashMap if (HashMap.containsKey(A[i])) HashMap.put(A[i], HashMap.get(A[i]) - 1); else HashMap.put(A[i], 1); // Performing operation on // current index int performOperation = A[i] & M; // Check if another element exists // with same value if (HashMap.get(performOperation)>0) return 1; // Inserting back occurrence // of element if (HashMap.containsKey(A[i])) HashMap.put(A[i], HashMap.get(A[i]) + 1); else HashMap.put(A[i], 1); } // Clearing the HashMap HashMap.clear(); for (int i = 0; i < N; i++) { // Performing operation on // current index int performOperation = A[i] & M; // Inserting this element // in Hashmap if (HashMap.containsKey(A[i])) HashMap.put(A[i], HashMap.get(A[i]) + 1); else HashMap.put(A[i], 1); // If two elements exist such that // both formed with operation if (HashMap.get(A[i]) == 2) return 2; } // If answer do not exist return -1; } // Driver Code public static void main(String args[]) { // Input 1 int A[] = { 1, 2, 3, 7 }; int N = A.length; int X = 3; // Function Call System.out.println(minOperations(A, N, X)); // Input 2 int A1[] = { 1, 2, 3 }; int N1 = A1.length; int X1 = 7; // Function Call System.out.println(minOperations(A1, N1, X1)); }} |
Output
1 -1
Time Complexity: O(N*logN)
Auxiliary Space: O(N)
Related Articles:
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
