Given an array arr[] consisting of N positive integers, the task is to find the nearest perfect power of 2 of the nearest perfect squares of unique array elements. If the array does not contain any unique element, then print -1.
Examples:
Input: arr[] = {4, 11, 4, 3, 4}
Output: 4 8
Explanation:
The unique elements in the given array are 11 and 3.
The nearest perfect square of 11 and 3 are 9 and 4 respectively.
The nearest power of 2 of 9 and 4 are 8 and 4 respectively.Input: arr[] = {1, 1, 2, 2, 3, 3}
Output: -1
Naive Approach: The simplest approach is to traverse the array and for each array element with single occurrence, print the nearest perfect power of 2 of the nearest perfect square of the array element. Otherwise, if there are no unique elements present in the array, then print -1.
Time Complexity: O(N2*log N)
Auxiliary Space: O(1)
Efficient Approach: The above can be optimized by Hashing. Follow the steps to solve the problem:
- Traverse the given array arr[] and store the frequency of each array element in a Map, say M.
- Traverse the map M and perform the following steps:
- If the frequency of the current element is 1, then print the nearest power of 2 of the nearest perfect square of the current element.
- Otherwise, continue to the next iteration.
- After completing the above steps, if there does not exist any unique elements in the above steps, then print “-1″.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find nearest// perfect square of numint perfectSquare(int num){ // Calculate square root of num int sr = sqrt(num); // Calculate perfect square int a = sr * sr; int b = (sr + 1) * (sr + 1); // Find the nearest perfect square if ((num - a) < (b - num)) { return a; } else { return b; }}// Function to find the power of 2// nearest to the number numint powerOfTwo(int num){ // Calculate log base 2 of num int lg = log2(num); // Highest power of 2 which is <= num int p = pow(2, lg); return p;}// Function to find the nearest perfect// square and the nearest power of 2 of// every array element whose occurrence is 1void uniqueElement(int arr[], int N){ bool ans = true; // Stores frequency of array elements unordered_map<int, int> freq; // Traverse the array and update // frequency of current array element for (int i = 0; i < N; i++) { freq[arr[i]]++; } // Traverse the map freq for (auto el : freq) { // If the frequency is 1 if (el.second == 1) { ans = false; // Find nearest perfect square int ps = perfectSquare(el.first); // Print the nearest power of 2 cout << powerOfTwo(ps) << ' '; } } // If the any does not contain // any non-repeating elements if (ans) cout << "-1";}// Driver Codeint main(){ int arr[] = { 4, 11, 4, 3, 4 }; 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 nearest // perfect square of num static int perfectSquare(int num) { // Calculate square root of num int sr = (int)(Math.sqrt(num)); // Calculate perfect square int a = sr * sr; int b = (sr + 1) * (sr + 1); // Find the nearest perfect square if ((num - a) < (b - num)) { return a; } else { return b; } } // Function to find the power of 2 // nearest to the number num static int powerOfTwo(int num) { // Calculate log base 2 of num int lg = (int)(Math.log(num) / Math.log(2)); // Highest power of 2 which is <= num int p = (int)(Math.pow(2, lg)); return p; } // Function to find the nearest perfect // square and the nearest power of 2 of // every array element whose occurrence is 1 static void uniqueElement(int arr[], int N) { boolean ans = true; // Stores frequency of array elements HashMap<Integer, Integer> freq = new HashMap<Integer, Integer>(); // Traverse the array and update // frequency of current array element 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); } } // Traverse the map freq for (Map.Entry<Integer, Integer> el : freq.entrySet()) { // If the frequency is 1 if (el.getValue() == 1) { ans = false; // Find nearest perfect square int ps = perfectSquare(el.getKey()); // Print the nearest power of 2 System.out.print(powerOfTwo(ps) + " "); } } // If the any does not contain // any non-repeating elements if (ans) System.out.print("-1"); } // Driver Code public static void main(String[] args) { int arr[] = { 4, 11, 4, 3, 4 }; int N = arr.length; uniqueElement(arr, N); }}// This code is contributed by subhammahato348. |
Python3
# Python3 program for the above approachfrom math import sqrt, log2, pow# Function to find nearest# perfect square of numdef perfectSquare(num): # Calculate square root of num sr = int(sqrt(num)) # Calculate perfect square a = sr * sr b = (sr + 1) * (sr + 1) # Find the nearest perfect square if ((num - a) < (b - num)): return a else: return b# Function to find the power of 2# nearest to the number numdef powerOfTwo(num): # Calculate log base 2 of num lg = int(log2(num)) # Highest power of 2 which is <= num p = int(pow(2, lg)) return p# Function to find the nearest perfect# square and the nearest power of 2 of# every array element whose occurrence is 1def uniqueElement(arr, N): ans = True # Stores frequency of array elements freq = {} # Traverse the array and update # frequency of current array element for i in range(N): if (arr[i] in freq): freq[arr[i]] += 1 else: freq[arr[i]] = 1 # Traverse the map freq res = [] for key,value in freq.items(): # If the frequency is 1 if (value == 1): ans = False # Find nearest perfect square ps = perfectSquare(key) # Print the nearest power of 2 res.append(powerOfTwo(ps)) res.sort(reverse = False) for x in res: print(x, end = " ") # If the any does not contain # any non-repeating elements if (ans): print("-1")# Driver Codeif __name__ == '__main__': arr = [4, 11, 4, 3, 4] N = len(arr) uniqueElement(arr, N)# This code is contributed by SURENDRA_GANGWAR |
C#
// C# program for the above approachusing System;using System.Collections.Generic;using System.Linq;class GFG{// Function to find nearest// perfect square of numstatic int perfectSquare(int num){ // Calculate square root of num int sr = (int)(Math.Sqrt(num)); // Calculate perfect square int a = sr * sr; int b = (sr + 1) * (sr + 1); // Find the nearest perfect square if ((num - a) < (b - num)) { return a; } else { return b; }}// Function to find the power of 2// nearest to the number numstatic int powerOfTwo(int num){ // Calculate log base 2 of num int lg = (int)(Math.Log(num) / Math.Log(2)); // Highest power of 2 which is <= num int p = (int)(Math.Pow(2, lg)); return p;}// Function to find the nearest perfect// square and the nearest power of 2 of// every array element whose occurrence is 1static void uniqueElement(int[] arr, int N){ bool ans = true; // Stores frequency of array elements Dictionary<int, int> freq = new Dictionary<int, int>(); // Traverse the array and update // frequency of current array element for(int i = 0; i < N; i++) { if (freq.ContainsKey(arr[i])) { freq[arr[i]] = freq[arr[i]] + 1; } else { freq[arr[i]] = 1; } } // Traverse the map freq foreach(var el in freq.OrderBy(el => el.Key)) { // If the frequency is 1 if (el.Value == 1) { ans = false; // Find nearest perfect square int ps = perfectSquare(el.Key); // Print the nearest power of 2 Console.Write(powerOfTwo(ps) + " "); } } // If the any does not contain // any non-repeating elements if (ans) Console.Write("-1");}// Driver Codepublic static void Main(string[] args){ int[] arr = { 4, 11, 4, 3, 4 }; int N = arr.Length; uniqueElement(arr, N);}}// This code is contributed by ukasp |
Javascript
<script>// Javascript program for the above approach// Function to find nearest// perfect square of numfunction perfectSquare(num) { // Calculate square root of num let sr = Math.floor(Math.sqrt(num)); // Calculate perfect square let a = sr * sr; let b = (sr + 1) * (sr + 1); // Find the nearest perfect square if ((num - a) < (b - num)) { return a; } else { return b; }}// Function to find the power of 2// nearest to the number numfunction powerOfTwo(num) { // Calculate log base 2 of num let lg = Math.floor(Math.log2(num)); // Highest power of 2 which is <= num let p = Math.pow(2, lg); return p;}// Function to find the nearest perfect// square and the nearest power of 2 of// every array element whose occurrence is 1function uniqueElement(arr, N){ let ans = true; arr.reverse(); // Stores frequency of array elements let freq = new Map(); // Traverse the array and update // frequency of current array element for(let i = 0; i < N; i++) { freq[arr[i]]++; if (freq.has(arr[i])) { freq.set(arr[i], freq.get(arr[i]) + 1) } else[ freq.set(arr[i], 1) ] } // Traverse the map freq for(let el of freq) { // If the frequency is 1 if (el[1] == 1) { ans = false; // Find nearest perfect square let ps = perfectSquare(el[0]); // Print the nearest power of 2 document.write(powerOfTwo(ps) + ' '); } } // If the any does not contain // any non-repeating elements if (ans) document.write("-1");}// Driver Codelet arr = [ 4, 11, 4, 3, 4 ];let N = arr.length;uniqueElement(arr, N);// This code is contributed by _saurabh_jaiswal</script> |
Output:
4 8
Time Complexity: O(N * log N)
Auxiliary Space: O(N)
