Dada una array arr[] que consta de N enteros positivos, la tarea es encontrar la potencia perfecta más cercana de 2 de los cuadrados perfectos más cercanos de elementos de array únicos . Si la array no contiene ningún elemento único, imprima -1 .
Ejemplos:
Entrada: arr[] = {4, 11, 4, 3, 4}
Salida: 4 8
Explicación:
Los elementos únicos en la array dada son 11 y 3.
El cuadrado perfecto más cercano de 11 y 3 son 9 y 4 respectivamente.
La potencia de 2 más cercana de 9 y 4 son 8 y 4 respectivamente.Entrada: arr[] = {1, 1, 2, 2, 3, 3}
Salida: -1
Enfoque ingenuo: el enfoque más simple es atravesar la array y, para cada elemento de la array con una sola ocurrencia, imprimir la potencia perfecta más cercana de 2 del cuadrado perfecto más cercano del elemento de la array. De lo contrario, si no hay elementos únicos presentes en la array, imprima -1 .
Complejidad de tiempo: O(N 2 *log N)
Espacio auxiliar: O(1)
Enfoque eficiente: lo anterior se puede optimizar mediante Hashing . Siga los pasos para resolver el problema:
- Recorra la array dada arr[] y almacene la frecuencia de cada elemento de la array en un Map , digamos M .
- Recorra el mapa M y realice los siguientes pasos:
- Si la frecuencia del elemento actual es 1 , imprima la potencia de 2 más cercana del cuadrado perfecto más cercano del elemento actual.
- De lo contrario, continúe con la siguiente iteración .
- Después de completar los pasos anteriores, si no existe ningún elemento único en los pasos anteriores, imprima » -1″ .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find nearest
// perfect square of num
int 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 num
int 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 1
void 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 Code
int 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 approach
import 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 approach
from math import sqrt, log2, pow
# Function to find nearest
# perfect square of num
def 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 num
def 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 1
def 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 Code
if __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 approach
using System;
using System.Collections.Generic;
using System.Linq;
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)
{
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 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 ukasp
Javascript
<script>
// Javascript program for the above approach
// Function to find nearest
// perfect square of num
function 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 num
function 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 1
function 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 Code
let arr = [ 4, 11, 4, 3, 4 ];
let N = arr.length;
uniqueElement(arr, N);
// This code is contributed by _saurabh_jaiswal
</script>
Producción:
4 8
Complejidad de tiempo: O(N * log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por subhammahato348 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA