Given an array arr[] of size N, the task is for every non-repeating array element is to find the highest power of 2 that does not exceed that element. Print the powers of 2 in ascending order. If the array does not contain any non-repeating element, print “0”.
Examples:
Input: arr[ ] = { 4, 5, 4, 3, 3, 4 }
Output: 4
Explanation: The only non-repeating element in the array is 5. Therefore, the highest power of 2 not exceeding 5 is 4.Input: arr[ ] = { 1, 1, 7, 6, 3 }
Output: 2 4 4
Naive Approach: The simplest approach to solve this problem is to traverse the array and for each array element, check if it is non-repeating or not. For elements founds to be non-repeating, add them into another array. Then, for each element in the new array, find the highest powers of 2 not exceeding that element and print them in ascending order.
Follow the steps below to implement the above idea:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to find the highest power of 2 for// every non-repeating element in the arrayvoid uniqueElement(int arr[], int N){ // For storing new repeating elements vector<int> newArr; // Finding all non- repeating elements for (int i = 0; i < N; i++) { bool flag = true; for (int j = 0; j < N; j++) { if (i == j) continue; if (arr[i] == arr[j]) { flag = false; break; } } if (flag) newArr.push_back(arr[i]); } // For storing the answer vector<int> result; // Traversing over all non-repeating elements for (auto val : newArr) { // Finding highest power of 2 in val int t = log2(val); result.push_back(pow(2, t)); } // Checking if size of result is zero if (result.size() == 0) { cout << 0 << endl; return; } // Sorting the result. sort(result.begin(), result.end()); // printing the result for (auto val : result) { cout << val << " "; }}// Driver Codeint main(){ int arr[] = { 1, 1, 7, 6, 3 }; // Size of array int N = sizeof(arr) / sizeof(arr[0]); uniqueElement(arr, N); return 0;} |
Java
import java.io.*;import java.util.*;public class Gfg { // Function to find the highest power of 2 for // every non-repeating element in the array static void uniqueElement(int arr[], int N) { // For storing new repeating elements List<Integer> newArr = new ArrayList<>(); // Finding all non- repeating elements for (int i = 0; i < N; i++) { boolean flag = true; for (int j = 0; j < N; j++) { if (i == j) continue; if (arr[i] == arr[j]) { flag = false; break; } } if (flag) newArr.add(arr[i]); } // For storing the answer List<Integer> result = new ArrayList<>(); // Traversing over all non-repeating elements for (int val : newArr) { // Finding highest power of 2 in val int t = (int)(Math.log(val) / Math.log(2)); result.add((int)Math.pow(2, t)); } // Checking if size of result is zero if (result.size() == 0) { System.out.println(0); return; } // Sorting the result. Collections.sort(result); // printing the result for (int val : result) { System.out.print(val + " "); } } // Driver Code public static void main(String[] args) { int arr[] = { 1, 1, 7, 6, 3 }; // Size of array int N = arr.length; uniqueElement(arr, N); }} |
Python3
# Python program to implement# the above approachimport math# Function to find the highest power of 2 for# every non-repeating element in the arraydef uniqueElement(arr, N): # For storing new repeating elements newAr = []; # Finding all non- repeating elements for i in range(0,N): flag = True; for j in range(0,N): if (i == j): continue; if (arr[i] == arr[j]): flag = False; break; if (flag): newAr.append(arr[i]); # For storing the answer result=[]; # Traversing over all non-repeating elements for i in range(0, len(newAr)) : val=newAr[i]; # Finding highest power of 2 in val t = int(math.log2(val)); result.append(int(pow(2, t))); # Checking if size of result is zero if (len(result) == 0) : print(0); return; # Sorting the result. result.sort(); # printing the result for i in range(0,len(result)): print(result[i], end=" "); # Driver Codearr = [ 1, 1, 7, 6, 3 ];# Size of arrayN = len(arr);uniqueElement(arr, N);# This code is contributed by ratiagrawal. |
C#
// C# implementation using System;using System.Collections.Generic;using System.Linq;using System.Text.RegularExpressions;public class Gfg{ // Function to find the highest power of 2 for // every non-repeating element in the array static void uniqueElement(int[] arr, int N) { // For storing new repeating elements List<int> newArr = new List<int>(); // Finding all non- repeating elements for (int i = 0; i < N; i++) { int flag = 1; for (int j = 0; j < N; j++) { if (i == j) continue; if (arr[i] == arr[j]) { flag = 0; break; } } if (flag == 1) newArr.Add(arr[i]); } // For storing the answer List<int> result = new List<int>(); // Traversing over all non-repeating elements for (int i = 0; i < newArr.Count; i++) { int val = newArr[i]; // Finding highest power of 2 in val int t = (int)(Math.Log(val,2)); result.Add((int)Math.Pow(2, t)); } // Checking if size of result is zero if (result.Count == 0) { Console.Write(0); return; } // Sorting the result. result.Sort(); // printing the result for (int i = 0; i < result.Count; i++) { Console.Write(result[i]+" "); } } // Driver Code public static void Main(string[] args) { int[] arr = { 1, 1, 7, 6, 3 }; // Size of array int N = arr.Length; uniqueElement(arr, N); }}// This code is contributed by poojaagarwal2. |
Javascript
// Javascript program to implement// the above approach// Function to find the highest power of 2 for// every non-repeating element in the arrayfunction uniqueElement(arr, N){ // For storing new repeating elements let newArr=[]; // Finding all non- repeating elements for (let i = 0; i < N; i++) { let flag = true; for (let j = 0; j < N; j++) { if (i == j) continue; if (arr[i] == arr[j]) { flag = false; break; } } if (flag) newArr.push(arr[i]); } // For storing the answer let result=[]; // Traversing over all non-repeating elements for (let i=0; i< newArr.length; i++) { // Finding highest power of 2 in val let t = Math.floor(Math.log2(newArr[i])); result.push(Math.pow(2, t)); } // Checking if size of result is zero if (result.length == 0) { document.write(0); return; } // Sorting the result. result.sort(); // printing the result for (let i=0; i<result.length; i++) { document.write(result[i] + " "); }}// Driver Code let arr = [1, 1, 7, 6, 3 ]; // Size of array let N = arr.length; uniqueElement(arr , N); |
Output
2 4 4
Time Complexity: O(N2 * log arr[i]), where arr[i] is the largest number of the array.
Auxiliary Space: O(N)
Efficient Approach: The optimal idea is to use Hashing. Follow the steps below to solve the problem:
- Traverse the array arr[] and store the frequency of each array element in a Map.
- Now, traverse the map and check if the frequency of any element is 1 or not.
- For all such elements, find the highest power of 2 not exceeding that element and store it in a vector.
- Sort the vector in ascending order and print the elements present in the vector.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to find the highest power of 2 for// every non-repeating element in the arrayvoid uniqueElement(int arr[], int N){ // Stores the frequency // of array elements unordered_map<int, int> freq; // Traverse the array for (int i = 0; i < N; i++) { // Update frequency of each // element of the array freq[arr[i]]++; } // Stores the non-repeating // array elements vector<int> v; // Traverse the Map for (auto i : freq) { if (i.second == 1) { // Calculate log base 2 // of the current element int lg = log2(i.first); // Highest power of 2 <= i.first int p = pow(2, lg); // Insert it into the vector v.push_back(p); } } // If no element is non-repeating if (v.size() == 0) { cout << "0"; return; } // Sort the powers of 2 obtained sort(v.begin(), v.end()); // Print the elements in the vector for (auto i : v) cout << i << " ";}// Driver Codeint main(){ int arr[] = { 4, 5, 4, 3, 3, 4 }; // Size of array int N = sizeof(arr) / sizeof(arr[0]); uniqueElement(arr, N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ // Function to find the highest power of 2 for // every non-repeating element in the array static void uniqueElement(int arr[], int N) { // Stores the frequency // of array elements HashMap<Integer, Integer> freq = new HashMap<Integer, Integer>(); for (int i = 0; i < N; i++) { if (freq.containsKey(arr[i])) { freq.put(arr[i], freq.get(arr[i]) + 1); } else { freq.put(arr[i], 1); } } // Stores the non-repeating // array elements ArrayList<Integer> v = new ArrayList<Integer>(); // Traverse the Map for (Map.Entry i : freq.entrySet()) { if ((int)i.getValue() == 1) { // Calculate log base 2 // of the current element int lg = (int)(Math.log((int)i.getKey()) / Math.log(2)); // Highest power of 2 <= i.first int p = (int)Math.pow(2, lg); // Insert it into the vector v.add(p); } } // If no element is non-repeating if (v.size() == 0) { System.out.print("0"); return; } // Sort the powers of 2 obtained Collections.sort(v); // Print the elements in the vector for (int i : v) System.out.print( i + " "); } // Driver Code public static void main(String[] args) { int arr[] = { 4, 5, 4, 3, 3, 4 }; // Size of array int N = arr.length; uniqueElement(arr, N); }}// This code is contributed by code_hunt. |
Python3
# Python3 program for the above approachimport math# Function to find the highest power of 2 for# every non-repeating element in the arraydef uniqueElement(arr, N): # Stores the frequency # of array elements freq = {} # Traverse the array for i in range(N) : # Update frequency # of arr[i] if arr[i] in freq : freq[arr[i]] += 1; else : freq[arr[i]] = 1; # Stores the non-repeating # array elements v = [] # Traverse the Map for i in freq : if (freq[i] == 1) : # Calculate log base 2 # of the current element lg = int(math.log2(i)) # Highest power of 2 <= i.first p = pow(2, lg) # Insert it into the vector v.append(p) # If no element is non-repeating if (len(v) == 0) : print("0") return # Sort the powers of 2 obtained v.sort() # Print elements in the vector for i in v : print(i, end = " ")# Driver Codearr = [ 4, 5, 4, 3, 3, 4 ]# Size of arrayN = len(arr)uniqueElement(arr, N)# This code is contributed by sanjoy_62. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG{ // Function to find the highest power of 2 for // every non-repeating element in the array static void uniqueElement(int []arr, int N) { // Stores the frequency // of array elements Dictionary<int, int> freq = new Dictionary<int, int>(); for (int i = 0; i < N; i++) { if (freq.ContainsKey(arr[i])) { freq[arr[i]] = freq[arr[i]] + 1; } else { freq.Add(arr[i], 1); } } // Stores the non-repeating // array elements List<int> v = new List<int>(); // Traverse the Map foreach(KeyValuePair<int, int> i in freq) { if ((int)i.Value == 1) { // Calculate log base 2 // of the current element int lg = (int)(Math.Log((int)i.Key) / Math.Log(2)); // Highest power of 2 <= i.first int p = (int)Math.Pow(2, lg); // Insert it into the vector v.Add(p); } } // If no element is non-repeating if (v.Count == 0) { Console.Write("0"); return; } // Sort the powers of 2 obtained v.Sort(); // Print the elements in the vector foreach (int i in v) Console.Write( i + " "); } // Driver Code public static void Main(String[] args) { int []arr = { 4, 5, 4, 3, 3, 4 }; // Size of array int N = arr.Length; uniqueElement(arr, N); }}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript program to implement// the above approach// Function to find the highest power of 2 for// every non-repeating element in the arrayfunction uniqueElement(arr, N){ // Stores the frequency // of array elements var freq = new Map(); // Traverse the array for (var i = 0; i < N; i++) { // Update frequency of each // element of the array if(freq.has(arr[i])) { freq.set(arr[i], freq.get(arr[i])+1); } else { freq.set(arr[i], 1); } } // Stores the non-repeating // array elements var v = []; // Traverse the Map freq.forEach((value, key) => { if (value== 1) { // Calculate log base 2 // of the current element var lg = parseInt(Math.log2(key)); // Highest power of 2 <= i.first var p = Math.pow(2, lg); // Insert it into the vector v.push(p); } }); // If no element is non-repeating if (v.length == 0) { document.write( "0"); return; } // Sort the powers of 2 obtained v.sort((a,b) => a-b) // Print the elements in the vector for(var i =0; i<v.length; i++) { document.write(v[i] + " "); } }// Driver Codevar arr = [4, 5, 4, 3, 3, 4 ];// Size of arrayvar N = arr.length;uniqueElement(arr, N);</script> |
Output:
4
Time Complexity: O(N * log(MAXM)), where MAXM is the largest element present the array.
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!
