Given an array arr[] consisting of N integers the task is to find the minimum number of elements that should be removed, such that for every remaining element arr[i], there exists another element arr[j], (i!=j) such that the sum of arr[i] and arr[j] is a power of 2. If after any number of deletions, no such pair exists, print -1.
Examples:
Input: arr[] ={1, 2, 3, 4, 5, 6}, N = 6
Output: 1
Explanation:
Removing 4 is sufficient as, for the remaining elements there exist an element such that their sum is a power of 2:
- For 1, there exists 3 such that (1+3=4) is a power of 2.
- For 2, there exists 6 such that (2+6=8) is a power of 2.
- For 3, there exists 1 such that (3+1=4) is a power of 2.
- For 5, there exists 3 such that (5+3=8) is a power of 2.
- For 6, there exists 2 such that (6+2=8) is a power of 2.
Input: A={1, 5, 10, 25, 50}, N=5
Output: -1
Approach: The idea is to use bitwise operators and the map to keep track of the frequencies of every element. Follow the steps below to solve the problem:
- Initialize a variable ans to 0, to store the number of elements to be removed.
- Calculate the frequency of all elements in arr[], and store them in a map say mp.
- Iterate from 0 to N-1, and for each current index i, do the following:
- Initialize a variable say flag to 0.
- Iterate from 0 to 30, and for each current index j, do the following:
- If the difference between 2j and arr[i] is equal to arr[i], and the frequency of arr[i] is greater than 1, increment flag and break.
- Otherwise, if the frequency of the difference between 2j and arr[i] is greater than 0, increment flag and break.
- If the flag is still 0, increment ans, as the current element needs to be removed.
- Finally, after completing the above steps, print the count of the removed element as the value obtained in ans, if it is less than equal to N. Else print -1.
Below is an implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to calculate the minimum // number of elements to be removed // satisfying the conditions int minimumDeletions( int arr[], int N) { // Stores the final answer int ans = 0; // Map to store frequency // of each element map< int , int > mp; // Traverse the array arr[] for ( int i = 0; i < N; i++) mp[arr[i]]++; // Traverse the array arr[] for ( int i = 0; i < N; i++) { // Stores whether current // element needs to be // removed or not int flag = 0; // Iterate over the range // [0, 30] for ( int j = 0; j < 31; j++) { // Stores 2^j int pw = (1 << j); // If 2^j -arr[i] equals // to the arr[i] if (pw - arr[i] == arr[i]) { // If count of arr[i] // is greater than 1 if (mp[arr[i]] > 1) { flag = 1; break ; } } // Else if count of 2^j-arr[i] // is greater than 0 else if (mp[pw - arr[i]] > 0) { flag = 1; break ; } } // If flag is 0 if (flag == 0) ans++; } // Return ans return ans == N ? -1 : ans; } // Driver Code int main() { int arr[] = { 1, 2, 3, 4, 5, 6 }; int N = sizeof (arr) / sizeof (arr[0]); cout << minimumDeletions(arr, N) << endl; int arr1[] = { 1, 5, 10, 25, 50 }; N = sizeof (arr) / sizeof (arr[0]); cout << minimumDeletions(arr1, N) << endl; return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to calculate the minimum // number of elements to be removed // satisfying the conditions static int minimumDeletions( int []arr, int N) { // Stores the final answer int ans = 0 ; // Map to store frequency // of each element Map<Integer, Integer> mp = new HashMap<Integer, Integer>(); // Traverse the array arr[] for ( int i = 0 ; i < N; i++){ if (mp.containsKey(arr[i])) mp.put(arr[i],mp.get(arr[i]) + 1 ); else mp.put(arr[i], 1 ); } // Traverse the array arr[] for ( int i = 0 ; i < N; i++) { // Stores whether current // element needs to be // removed or not int flag = 0 ; // Iterate over the range // [0, 30] for ( int j = 0 ; j < 31 ; j++) { // Stores 2^j int pw = ( 1 << j); // If 2^j -arr[i] equals // to the arr[i] if (pw - arr[i] == arr[i]) { // If count of arr[i] // is greater than 1 if (mp.containsKey(arr[i]) && mp.get(arr[i]) > 1 ) { flag = 1 ; break ; } } // Else if count of 2^j-arr[i] // is greater than 0 else if (mp.containsKey(pw - arr[i]) && mp.get(pw - arr[i]) > 0 ) { flag = 1 ; break ; } } // If flag is 0 if (flag == 0 ) ans++; } // Return ans if (ans == N) return - 1 ; else return ans; } // Driver Code public static void main(String[] args) { int arr[] = { 1 , 2 , 3 , 4 , 5 , 6 }; int N = arr.length; System.out.println(minimumDeletions(arr, N)); int arr1[] = { 1 , 5 , 10 , 25 , 50 }; N = arr1.length; System.out.print(minimumDeletions(arr1, N)); } } // This code is contributed by ShubhamSingh10 |
Python3
# Py program for the above approach # Function to calculate the minimum # number of elements to be removed # satisfying the conditions def minimumDeletions(arr, N): # Stores the final answer ans = 0 # Map to store frequency # of each element mp = {} # Traverse the array arr[] for i in arr: mp[i] = mp.get(i, 0 ) + 1 # Traverse the array arr[] for i in range (N): # Stores whether current # element needs to be # removed or not flag = 0 # Iterate over the range # [0, 30] for j in range ( 31 ): # Stores 2^j pw = ( 1 << j) # If 2^j -arr[i] equals # to the arr[i] if i > = len (arr): break if (pw - arr[i] = = arr[i]): # If count of arr[i] # is greater than 1 if (mp[arr[i]] > 1 ): flag = 1 break # Else if count of 2^j-arr[i] # is greater than 0 elif (((pw - arr[i]) in mp) and mp[pw - arr[i]] > 0 ): flag = 1 break # If flag is 0 if (flag = = 0 ): ans + = 1 # Return ans return - 1 if ans = = N else ans # Driver Code if __name__ = = '__main__' : arr = [ 1 , 2 , 3 , 4 , 5 , 6 ] N = len (arr) print (minimumDeletions(arr, N)) arr1 = [ 1 , 5 , 10 , 25 , 50 ] N = len (arr) print (minimumDeletions(arr1, N)) # This code is contributed by mohit kumar 29. |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to calculate the minimum // number of elements to be removed // satisfying the conditions static int minimumDeletions( int []arr, int N) { // Stores the final answer int ans = 0; // Map to store frequency // of each element Dictionary< int , int > mp = new Dictionary< int , int >(); // Traverse the array arr[] for ( int i = 0; i < N; i++){ if (mp.ContainsKey(arr[i])) mp[arr[i]] += 1; else mp.Add(arr[i],1); } // Traverse the array arr[] for ( int i = 0; i < N; i++) { // Stores whether current // element needs to be // removed or not int flag = 0; // Iterate over the range // [0, 30] for ( int j = 0; j < 31; j++) { // Stores 2^j int pw = (1 << j); // If 2^j -arr[i] equals // to the arr[i] if (pw - arr[i] == arr[i]) { // If count of arr[i] // is greater than 1 if (mp.ContainsKey(arr[i]) && mp[arr[i]] > 1) { flag = 1; break ; } } // Else if count of 2^j-arr[i] // is greater than 0 else if (mp.ContainsKey(pw - arr[i]) && mp[pw - arr[i]] > 0) { flag = 1; break ; } } // If flag is 0 if (flag == 0) ans++; } // Return ans if (ans == N) return -1; else return ans; } // Driver Code public static void Main() { int []arr = { 1, 2, 3, 4, 5, 6 }; int N = arr.Length; Console.WriteLine(minimumDeletions(arr, N)); int []arr1 = { 1, 5, 10, 25, 50 }; N = arr1.Length; Console.Write(minimumDeletions(arr1, N)); } } // This code is contributed by SURENDRA_GANGWAR. |
Javascript
<script> // JavaScript program for the above approach // Function to calculate the minimum // number of elements to be removed // satisfying the conditions function minimumDeletions(arr, N) { // Stores the final answer let ans = 0; // Map to store frequency // of each element let mp = new Map(); // Traverse the array arr[] for (let i = 0; i < N; i++) { if (mp.has(arr[i])) { mp.set(arr[i], mp.get(arr[i]) + 1) } else { mp.set(arr[i], 1) } } // Traverse the array arr[] for (let i = 0; i < N; i++) { // Stores whether current // element needs to be // removed or not let flag = 0; // Iterate over the range // [0, 30] for (let j = 0; j < 31; j++) { // Stores 2^j let pw = (1 << j); // If 2^j -arr[i] equals // to the arr[i] if (pw - arr[i] == arr[i]) { // If count of arr[i] // is greater than 1 if (mp.get(arr[i]) > 1) { flag = 1; break ; } } // Else if count of 2^j-arr[i] // is greater than 0 else if (mp.get(pw - arr[i]) > 0) { flag = 1; break ; } } // If flag is 0 if (flag == 0) ans++; } // Return ans return ans == N ? -1 : ans; } // Driver Code let arr = [1, 2, 3, 4, 5, 6]; let N = arr.length; document.write(minimumDeletions(arr, N) + "<br>" ); let arr1 = [1, 5, 10, 25, 50]; N = arr.length; document.write(minimumDeletions(arr1, N) + "<br>" ); </script> |
1 -1
Time Complexity: O(N*log(N))
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!