Given an array arr[] of length N, the task is to print the number of array elements that cannot form a pair with any other array element whose sum is a power of two.
Examples:
Input: arr[] = {6, 2, 11}
Output: 1
Explanation:
Since 6 and 2 can form a pair with sum 8 (= 23). So only 11 has to be removed as it does not form a sum which is a power of 2.
Input: arr[] = [1, 1, 1, 1023],
Output: 0
Explanation:
The given array elements can be split into following two pairs:
(1, 1) with sum 2(= 21)
(1, 1023) with sum 1024(= 210)
Hence, no need to remove any element.
Approach:
To solve the problem mentioned above, follow the steps below:
- Store the frequencies of all array elements in a Map.
- For every array element a[i], iterate over all possible sums p = {20, 21, …., 230} and check if p – a[i] is present in the array or not.
- Either of the following two conditions needs to be satisfied:
- Let s = p – a[i]. If s is present in the array more than once, then a pair consisting of a[i] with sum p is possible.
- If s is present only once in the array, then s has to be different from a[i] for a possible pair.
- If none of the above two conditions are satisfied, no pair consisting of a[i] is possible with sum p.
- If the above two conditions do not satisfy for any p for the current a[i], then increase the count as a[i] cannot form a sum which is a power of 2 with any other array element.
- Print the final value of count.
Below is the implementation of the above approach:
C++
// C++ Program to count of// array elements which do// not form a pair with sum// equal to a power of 2// with any other array element#include <bits/stdc++.h>using namespace std;// Function to calculate// and return the// count of elementsint powerOfTwo(int a[], int n){ // Stores the frequencies // of every array element map<int, int> mp; for (int i = 0; i < n; i++) mp[a[i]]++; // Stores the count // of removals int count = 0; for (int i = 0; i < n; i++) { bool f = false; // For every element, check if // it can form a sum equal to // any power of 2 with any other // element for (int j = 0; j < 31; j++) { // Store pow(2, j) - a[i] int s = (1 << j) - a[i]; // Check if s is present // in the array if (mp.count(s) // If frequency of s // exceeds 1 && (mp[s] > 1 // If s has frequency 1 // but is different from // a[i] || mp[s] == 1 && s != a[i])) // Pair possible f = true; } // If no pair possible for // the current element if (f == false) count++; } // Return the answer return count;}// Driver Codeint main(){ int a[] = { 6, 2, 11 }; int n = sizeof(a) / sizeof(a[0]); cout << powerOfTwo(a, n); return 0;} |
Java
// Java program to count of array// elements which do not form a // pair with sum equal to a power// of 2 with any other array elementimport java.util.*;class GFG{// Function to calculate and return// the count of elementsstatic int powerOfTwo(int a[], int n){ // Stores the frequencies // of every array element HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>(); for(int i = 0; i < n; i++) { if(mp.containsKey(a[i])) { mp.put(a[i], mp.get(a[i]) + 1); } else { mp.put(a[i], 1); } } // Stores the count // of removals int count = 0; for(int i = 0; i < n; i++) { boolean f = false; // For every element, check if // it can form a sum equal to // any power of 2 with any other // element for(int j = 0; j < 31; j++) { // Store Math.pow(2, j) - a[i] int s = (1 << j) - a[i]; // Check if s is present // in the array if (mp.containsKey(s) && // If frequency of s // exceeds 1 (mp.get(s) > 1 || // If s has frequency 1 // but is different from // a[i] mp.get(s) == 1 && s != a[i])) // Pair possible f = true; } // If no pair possible for // the current element if (f == false) count++; } // Return the answer return count;}// Driver Codepublic static void main(String[] args){ int a[] = { 6, 2, 11 }; int n = a.length; System.out.print(powerOfTwo(a, n));}}// This code is contributed by Amit Katiyar |
Python3
# Python3 program to count of# array elements which do# not form a pair with sum# equal to a power of 2# with any other array elementfrom collections import defaultdict# Function to calculate# and return the# count of elementsdef powerOfTwo(a, n): # Stores the frequencies # of every array element mp = defaultdict (int) for i in range (n): mp[a[i]] += 1 # Stores the count # of removals count = 0 for i in range (n): f = False # For every element, check if # it can form a sum equal to # any power of 2 with any other # element for j in range (31): # Store pow(2, j) - a[i] s = (1 << j) - a[i] # Check if s is present # in the array if (s in mp # If frequency of s # exceeds 1 and (mp[s] > 1 # If s has frequency 1 # but is different from # a[i] or mp[s] == 1 and s != a[i])): # Pair possible f = True # If no pair possible for # the current element if (f == False): count += 1 # Return the answer return count# Driver Codeif __name__ == "__main__": a = [6, 2, 11] n = len(a) print(powerOfTwo(a, n))# This code is contributed by Chitranayal |
C#
// C# program to count of array// elements which do not form a // pair with sum equal to a power// of 2 with any other array elementusing System;using System.Collections.Generic;class GFG{// Function to calculate and return// the count of elementsstatic int powerOfTwo(int []a, int n){ // Stores the frequencies // of every array element Dictionary<int, int> mp = new Dictionary<int, int>(); for(int i = 0; i < n; i++) { if(mp.ContainsKey(a[i])) { mp[a[i]] = mp[a[i]] + 1; } else { mp.Add(a[i], 1); } } // Stores the count // of removals int count = 0; for(int i = 0; i < n; i++) { bool f = false; // For every element, check if // it can form a sum equal to // any power of 2 with any other // element for(int j = 0; j < 31; j++) { // Store Math.Pow(2, j) - a[i] int s = (1 << j) - a[i]; // Check if s is present // in the array if (mp.ContainsKey(s) && // If frequency of s // exceeds 1 (mp[s] > 1 || // If s has frequency 1 // but is different from // a[i] mp[s] == 1 && s != a[i])) // Pair possible f = true; } // If no pair possible for // the current element if (f == false) count++; } // Return the answer return count;}// Driver Codepublic static void Main(String[] args){ int []a = { 6, 2, 11 }; int n = a.Length; Console.Write(powerOfTwo(a, n));}}// This code is contributed by Amit Katiyar |
Javascript
<script>// Javascript program to count of array// elements which do not form a// pair with sum equal to a power// of 2 with any other array element// Function to calculate and return// the count of elementsfunction powerOfTwo(a, n){ // Stores the frequencies // of every array element let mp = new Map(); for(let i = 0; i < n; i++) { if(mp.has(a[i])) { mp.set(a[i], mp.get(a[i]) + 1); } else { mp.set(a[i], 1); } } // Stores the count // of removals let count = 0; for(let i = 0; i < n; i++) { let f = false; // For every element, check if // it can form a sum equal to // any power of 2 with any other // element for(let j = 0; j < 31; j++) { // Store Math.pow(2, j) - a[i] let s = (1 << j) - a[i]; // Check if s is present // in the array if (mp.has(s) && // If frequency of s // exceeds 1 (mp.get(s) > 1 || // If s has frequency 1 // but is different from // a[i] mp.get(s) == 1 && s != a[i])) // Pair possible f = true; } // If no pair possible for // the current element if (f == false) count++; } // Return the answer return count;}// Driver code let a = [ 6, 2, 11 ]; let n = a.length; document.write(powerOfTwo(a, n)); // This code is contributed by sourabhghosh0416.</script> |
Output:
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!
