Dada una array arr[] de tamaño N , la tarea para cada elemento de la array que no se repite es encontrar la potencia más alta de 2 que no exceda ese elemento . Imprime las potencias de 2 en orden ascendente. Si la array no contiene ningún elemento que no se repita , imprima «0» .
Ejemplos:
Entrada: arr[ ] = { 4, 5, 4, 3, 3, 4 }
Salida: 4
Explicación: El único elemento que no se repite en la array es 5. Por lo tanto, la potencia más alta de 2 que no excede 5 es 4.Entrada: arr[ ] = { 1, 1, 7, 6, 3 }
Salida: 2 4 4
Enfoque ingenuo: el enfoque más simple para resolver este problema es atravesar la array y, para cada elemento de la array, verificar si no se repite o no. Para que los elementos no se repitan, agréguelos a otra array. Luego, para cada elemento en la nueva array, encuentre las potencias más altas de 2 que no excedan ese elemento e imprímalas en orden ascendente.
Complejidad de tiempo: O(N 2 * log arr[i]), donde arr[i] es el número más grande de la array.
Espacio Auxiliar: O(N)
Enfoque eficiente: la idea óptima es utilizar Hashing . Siga los pasos a continuación para resolver el problema:
- Recorra la array arr[] y almacene la frecuencia de cada elemento de la array en un mapa .
- Ahora, recorra el mapa y verifique si la frecuencia de cualquier elemento es 1 o no.
- Para todos esos elementos, encuentre la potencia más alta de 2 que no exceda ese elemento y guárdela en un vector .
- Ordene el vector en orden ascendente e imprima los elementos presentes en el vector.
A continuación se muestra la implementación del enfoque anterior:
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 array
void 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 Code
int 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 approach
import 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 approach
import math
# Function to find the highest power of 2 for
# every non-repeating element in the array
def 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 Code
arr = [ 4, 5, 4, 3, 3, 4 ]
# Size of array
N = len(arr)
uniqueElement(arr, N)
# This code is contributed by sanjoy_62.
C#
// C# program for the above approach
using 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 array
function 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 Code
var arr = [4, 5, 4, 3, 3, 4 ];
// Size of array
var N = arr.length;
uniqueElement(arr, N);
</script>
Producción:
4
Complejidad de tiempo: O(N * log(MAXM)), donde MAXM es el elemento más grande presente en la array .
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