Número de pares cuya suma es una potencia de 2 | conjunto 2

Dada una array arr[] que consta de N enteros, la tarea es contar el número máximo de pares (arr[i], arr[j]) tal que arr[i] + arr[j] sea una potencia de 2 .

Ejemplos:

Entrada: arr[] = {1, -1, 2, 3}
Salida: 5
Explicación: (1, 1), (2, 2), (1, 3), (-1, 3), (-1, 2) son los pares válidos cuya suma es potencia de 2.

Entrada: arr[] = {1, 1, 1}
Salida: 6

Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todos los pares posibles a partir de una array dada y, para cada par, verificar si la suma del par es una potencia de 2 o no
Complejidad de Tiempo: O(N 2
Espacio Auxiliar: O(1)

Enfoque eficiente: el enfoque anterior se puede optimizar utilizando HashMap . Siga los pasos a continuación para resolver el problema:

  • Cree un mapa para almacenar la frecuencia de cada elemento de la array arr[] .
  • Inicialice una variable ans para almacenar el recuento de pares con una suma igual a cualquier potencia de 2 .
  • Atraviesa el rango [0, 31] y genera todas las potencias de 2, es decir, 2 0 a 2 31 .
  • Recorra la array dada para cada potencia de 2 generada y verifique si map[key – arr[j]] existe o no, donde key es igual a 2 i .
  • Si se determina que es cierto, aumente la cuenta en map[key – arr[j]] , ya que existen pares ( arr[j], key – arr[j]) con una suma igual a una potencia de 2 .
  • Finalmente, imprima count / 2 como la respuesta requerida.

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 count all pairs
// whose sum is a power of two
int countPair(int arr[], int n)
{
    // Stores the frequency of
    // each element of the array
    map<int, int> m;
 
    // Update frequency of
    // array elements
    for (int i = 0; i < n; i++)
        m[arr[i]]++;
 
    // Stores count of
    // required pairs
    int ans = 0;
 
    for (int i = 0; i < 31; i++) {
 
        // Current power of 2
        int key = pow(2, i);
 
        // Traverse the array
        for (int j = 0; j < n; j++) {
 
            int k = key - arr[j];
 
            // If pair does not exist
            if (m.find(k) == m.end())
                continue;
 
            // Increment count of pairs
            else
                ans += m[k];
 
            if (k == arr[j])
                ans++;
        }
    }
 
    // Return the count of pairs
    return ans / 2;
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 8, 2, 10, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << countPair(arr, n) << endl;
 
    return 0;
}

Java

// Java program to implement
// the above approach
import java.util.*;
 
class GFG {
    // Function to count all pairs
    // whose sum is power of two
    static int countPair(int[] arr, int n)
    {
        // Stores the frequency of
        // each element of the array
        Map<Integer, Integer> m
            = new HashMap<>();
 
        // Update the frequency of
        // array elements
        for (int i = 0; i < n; i++)
            m.put(arr[i], m.getOrDefault(
                            arr[i], 0)
                            + 1);
 
        // Stores the count of pairs
        int ans = 0;
 
        // Generate powers of 2
        for (int i = 0; i < 31; i++) {
 
            // Generate current power of 2
            int key = (int)Math.pow(2, i);
 
            // Traverse the array
            for (int j = 0; j < arr.length;
                j++) {
 
                int k = key - arr[j];
 
                // Increase ans by m[k], if
                // pairs with sum 2^i exists
                ans += m.getOrDefault(k, 0);
 
                // Increase ans again if k = arr[j]
                if (k == arr[j])
                    ans++;
            }
        }
 
        // Return count of pairs
        return ans / 2;
    }
 
    // Driver function
    public static void main(String[] args)
    {
        int[] arr = { 1, -1, 2, 3 };
        int n = arr.length;
        System.out.println(countPair(arr, n));
    }
}

Python3

# Python3 program to implement
# the above approach
from math import pow
 
# Function to count all pairs
# whose sum is a power of two
def countPair(arr, n):
     
    # Stores the frequency of
    # each element of the array
    m = {}
 
    # Update frequency of
    # array elements
    for i in range(n):
        m[arr[i]] = m.get(arr[i], 0) + 1
 
    # Stores count of
    # required pairs
    ans = 0
 
    for i in range(31):
         
        # Current power of 2
        key = int(pow(2, i))
 
        # Traverse the array
        for j in range(n):
            k = key - arr[j]
 
            # If pair does not exist
            if k not in m:
                continue
 
            # Increment count of pairs
            else:
                ans += m.get(k, 0)
 
            if (k == arr[j]):
                ans += 1
 
    # Return the count of pairs
    return ans // 2
 
# Driver Code
if __name__ == '__main__':
     
    arr =  [ 1, 8, 2, 10, 6 ]
    n = len(arr)
     
    print(countPair(arr, n))
 
# This code is contributed by SURENDRA_GANGWAR

Javascript

<script>
 
// JavaScript program to implement
// the above approach
 
// Function to count all pairs
// whose sum is a power of two
function countPair(arr, n)
{
    // Stores the frequency of
    // each element of the array
    var m= new Map();
 
    // Update frequency of
    // array elements
    for (var i = 0; i < n; i++)
    {
        if(m.has(arr[i]))
            m.set(arr[i], m.get(arr[i])+1)
        else
            m.set(arr[i], 1)
    }
 
    // Stores count of
    // required pairs
    var ans = 0;
 
    for (var i = 0; i < 31; i++) {
 
        // Current power of 2
        var key = Math.pow(2, i);
 
        // Traverse the array
        for (var j = 0; j < n; j++) {
 
            var k = key - arr[j];
 
            // If pair does not exist
            if (!m.has(k))
                continue;
 
            // Increment count of pairs
            else
                ans += m.get(k);
 
            if (k == arr[j])
                ans++;
        }
    }
 
    // Return the count of pairs
    return ans / 2;
}
 
// Driver Code
var arr = [1, 8, 2, 10, 6]
var n = arr.length
document.write( countPair(arr, n));
 
</script>

C#

// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
 
class GFG {
 
    // Function to count all pairs
    // whose sum is a power of two
    public static int countPair(int[] arr, int n)
    { // Stores the frequency of
        // each element of the array
        Dictionary<int, int> map
            = new Dictionary<int, int>();
 
        // Update frequency of
        // array elements
        for (int i = 0; i < n; i++) {
 
            if (!map.ContainsKey(arr[i])) {
                map[arr[i]] = 0;
            }
 
            map[arr[i]] = map[arr[i]] + 1;
        }
        // Stores count of
        // required pairs
        int ans = 0;
 
        for (int i = 0; i < 31; i++) {
            // Current power of 2
            int key = 1 << i;
 
            // Traverse the array
            for (int j = 0; j < n; j++) {
                int k = key - arr[j];
 
                // If pair does not exist
                if (!map.ContainsKey(k)) {
                    continue;
                }
                else {
                    // Increment count of pairs
                    ans += map[k];
                }
 
                if (k == arr[j]) {
                    ans++;
                }
            }
        }
 
        // Return the count of pairs
        return ans / 2;
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        int[] arr = { 1, 8, 2, 10, 6 };
        int n = arr.Length;
        Console.WriteLine(countPair(arr, n));
    }
}
 
// This code is contributed by Naveen Shah
Producción

5

 

Producción:

5

Complejidad Temporal: O(NlogN)
Espacio Auxiliar: O(N). Estamos usando un mapa para almacenar elementos.

Publicación traducida automáticamente

Artículo escrito por offbeat 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 *