Potencia más cercana de 2 de los cuadrados perfectos más cercanos de elementos de array que no se repiten

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:

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *