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 conditionsint 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 Codeint 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 approachimport 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 conditionsdef 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 Codeif __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 approachusing System;using System.Collections.Generic;class GFG{// Function to calculate the minimum// number of elements to be removed// satisfying the conditionsstatic 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 Codepublic 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 conditionsfunction 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 Codelet 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> |
Output:
1 -1
Time Complexity: O(N*log(N))
Auxiliary Space: O(N)
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!
