Count array elements whose highest power of 2 less than or equal to that number is present in the given array
Given an array arr[] consisting of N positive integers, the task is to find the number of array elements whose highest power of 2 less than or equal to that number is present in the array.
Examples:
Input: arr[] = {3, 4, 6, 9}
Output: 2
Explanation:
There are 2 array elements (4 and 6), whose highest power of 2 is less than it (i.e. 4) are present in the array.Input: arr[] = {3, 9, 10, 8, 1}
Output: 3
Naive Approach: The given problem can be solved by count those elements whose highest power of 2 exists in the given array and that can be found by traversing the array again. After checking for all the elements, print the total count obtained.
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: The above approach can also be optimized by using an unordered_map to keep the count of visited elements and update the count of resultant elements accordingly. Follow the steps below to solve the given problem:
- Initialize a variable, say count that stores the count of elements whose highest power of 2 less than or equals to that is present in the array.
- Initialize a map M and store the frequency of array elements.
- Traverse the given array and for each element, if the frequency of the highest power of 2 of arr[i] not exceeding the element exists in the map then increment the value of count by 1.
- After completing the above steps, print the value of count as the resultant count of elements.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count array elements // whose highest power of 2 is less // than or equal to that number is // present in the given array int countElement( int arr[], int N) { // Stores the resultant count // of array elements int count = 0; // Stores frequency of // visited array elements unordered_map< int , int > m; // Traverse the array for ( int i = 0; i < N; i++) { m[arr[i]]++; } for ( int i = 0; i < N; i++) { // Calculate log base 2 // of the element arr[i] int lg = log2(arr[i]); // Highest power of 2 whose // value is at most arr[i] int p = pow (2, lg); // Increment the count by 1 if (m[p]) { count++; } } // Return the resultant count return count; } // Driver Code int main() { int arr[] = { 3, 4, 6, 9 }; int N = sizeof (arr) / sizeof (arr[0]); cout << countElement(arr, N); return 0; } |
Java
// Java program for the above approach import java.util.HashMap; import java.io.*; class GFG{ static int log2( int N) { // Calculate log2 N indirectly // using log() method int result = ( int )(Math.log(N) / Math.log( 2 )); return result; } // Function to count array elements // whose highest power of 2 is less // than or equal to that number is // present in the given array static int countElement( int arr[], int N) { // Stores the resultant count // of array elements int count = 0 ; // Stores frequency of // visited array elements HashMap<Integer, Integer> m = new HashMap<>(); // Traverse the array for ( int i = 0 ; i < N; i++) { if (m.containsKey(arr[i])) { m.put(arr[i], m.get(arr[i]) + 1 ); } else { m.put(arr[i], 1 ); } } for ( int i = 0 ; i < N; i++) { // Calculate log base 2 // of the element arr[i] int lg = log2(arr[i]); // Highest power of 2 whose // value is at most arr[i] int p = ( int )Math.pow( 2 , lg); // Increment the count by 1 if (m.containsKey(p)) { count++; } } // Return the resultant count return count; } // Driver Code public static void main (String[] args) { int arr[] = { 3 , 4 , 6 , 9 }; int N = arr.length; System.out.println(countElement(arr, N)); } } // This code is contributed by Potta Lokesh |
Python3
# Python program for the above approach from math import log2 # Function to count array elements # whose highest power of 2 is less # than or equal to that number is # present in the given array def countElement(arr, N): # Stores the resultant count # of array elements count = 0 # Stores frequency of # visited array elements m = {} # Traverse the array for i in range (N): m[arr[i]] = m.get(arr[i], 0 ) + 1 for i in range (N): # Calculate log base 2 # of the element arr[i] lg = int (log2(arr[i])) # Highest power of 2 whose # value is at most arr[i] p = pow ( 2 , lg) # Increment the count by 1 if (p in m): count + = 1 # Return the resultant count return count # Driver Code if __name__ = = '__main__' : arr = [ 3 , 4 , 6 , 9 ] N = len (arr) print (countElement(arr, 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 count array elements // whose highest power of 2 is less // than or equal to that number is // present in the given array static int countElement( int []arr, int N) { // Stores the resultant count // of array elements int count = 1; // Stores frequency of // visited array elements Dictionary< int , int > m = new Dictionary< int , int >(); // Traverse the array for ( int i = 0; i < N; i++) { if (m.ContainsKey(arr[i])) m[arr[i]]++; else m.Add(arr[i],1); } for ( int i = 0; i < N; i++) { // Calculate log base 2 // of the element arr[i] int lg = ( int )Math.Log(arr[i]); // Highest power of 2 whose // value is at most arr[i] int p = ( int )Math.Pow(2, lg); // Increment the count by 1 if (m.ContainsKey(p)) { count++; } } // Return the resultant count return count; } // Driver Code public static void Main() { int []arr = { 3, 4, 6, 9 }; int N = arr.Length; Console.Write(countElement(arr, N)); } } // This code is contributed by bgangwar59. |
Javascript
<script> // Javascript program for the above approach // Function to count array elements // whose highest power of 2 is less // than or equal to that number is // present in the given array function countElement(arr, N) { // Stores the resultant count // of array elements let count = 0; // Stores frequency of // visited array elements let m = new Map(); // Traverse the array for (let i = 0; i < N; i++) { if (m.has(arr[i])) { m.set(arr[i], m.get(arr[i]) + 1) } else { m.set(arr[i], 1) } } for (let i = 0; i < N; i++) { // Calculate log base 2 // of the element arr[i] let lg = Math.floor(Math.log2(arr[i])); // Highest power of 2 whose // value is at most arr[i] let p = Math.pow(2, lg); // Increment the count by 1 if (m.get(p)) { count++; } } // Return the resultant count return count; } // Driver Code let arr = [3, 4, 6, 9]; let N = arr.length document.write(countElement(arr, N)); // This code is contributed by _saurabh_jaiswal. </script> |
2
Time Complexity: O(N)
Auxiliary Space: O(N)