Dada una array arr[] que consta de N potencias de 2 , la tarea es contar el número de pares (arr[i], arr[j]) tales que i < j y arr[j] es divisible por arr[i] .
Ejemplos:
Entrada: arr[] = {4, 16, 8, 64}
Salida: 5
Explicación:
Los pares que satisfacen la condición dada son {4, 16}, {4, 8}, {4, 64}, {16, 64} , {8, 64}.Entrada: arr[] = {2, 4, 8, 16}
Salida: 6
Explicación:
Los pares que satisfacen la condición dada son {2, 4}, {2, 8}, {2, 16}, {4, 8} , {4, 16}, {8, 16}.
Enfoque ingenuo: el enfoque más simple es generar todos los pares de la array dada arr[] y, para cada par, comprobar si arr[j] % arr[i] es 0 o no. Si es cierto, incremente el conteo en 1. Finalmente, imprima el valor del conteo después de verificar todos los pares.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea se basa en la observación de que cualquier potencia de 2 tiene solo un bit establecido en su representación binaria . Para cualquier elemento arr[j] , todas las potencias de 2 que tienen sus bits establecidos en una posición menor o igual a la posición de un bit establecido de arr[j] , satisfarán la condición dada. Siga los pasos a continuación para resolver el problema:
- Inicialice una array auxiliar setBits de tamaño igual a 31 e inicialice count como 0 para almacenar la cantidad de pares requeridos.
- Recorra el arreglo arr[] usando la variable i y realice las siguientes operaciones:
- Almacene el bit establecido más a la izquierda de arr[i] en bitPos .
- Iterar en el rango [0, bitPos] usando la variable j e incrementar el conteo en setBits[j] en cada paso.
- Incremente setBits[bitPos] en 1 .
- Después de completar los pasos anteriores, imprima el valor de conteo como resultado.
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 count the number of
// pairs as per the given conditions
void numberOfPairs(int arr[], int N)
{
// Initialize array set_bits as 0
int set_bits[31] = { 0 };
// Store the total number of
// required pairs
int count = 0;
// Traverse the array arr[]
for (int i = 0; i < N; i++) {
// Store arr[i] in x
int x = arr[i];
// Store the position of the
// leftmost set bit in arr[i]
int bitpos = -1;
while (x > 0) {
// Increase bit position
bitpos++;
// Divide by 2 to shift bits
// in right at each step
x /= 2;
}
// Count of pairs for index i
// till its set bit position
for (int j = 0;
j <= bitpos; j++) {
count += set_bits[j];
}
// Increasing count of set bit
// position of current element
set_bits[bitpos]++;
}
// Print the answer
cout << count;
}
// Driver Code
int main()
{
int arr[] = { 4, 16, 8, 64 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
numberOfPairs(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to count the number of
// pairs as per the given conditions
static void numberOfPairs(int arr[], int N)
{
// Initialize array set_bits as 0
int []set_bits = new int[31];
Arrays.fill(set_bits, 0);
// Store the total number of
// required pairs
int count = 0;
// Traverse the array arr[]
for (int i = 0; i < N; i++)
{
// Store arr[i] in x
int x = arr[i];
// Store the position of the
// leftmost set bit in arr[i]
int bitpos = -1;
while (x > 0)
{
// Increase bit position
bitpos++;
// Divide by 2 to shift bits
// in right at each step
x /= 2;
}
// Count of pairs for index i
// till its set bit position
for (int j = 0;
j <= bitpos; j++)
{
count += set_bits[j];
}
// Increasing count of set bit
// position of current element
set_bits[bitpos]++;
}
// Print the answer
System.out.println(count);
}
// Driver Code
public static void main(String args[])
{
int arr[] = { 4, 16, 8, 64 };
int N = arr.length;
// Function Call
numberOfPairs(arr, N);
}
}
// This code is contributed by SURENDRA_GANGWAR.
Python3
# Python3 program for the above approach # Function to count the number of # pairs as per the given conditions def numberOfPairs(arr, N): # Initialize array set_bits as 0 set_bits = [0]*31 # Store the total number of # required pairs count = 0 # Traverse the array arr[] for i in range(N): # Store arr[i] in x x = arr[i] # Store the position of the # leftmost set bit in arr[i] bitpos = -1 while (x > 0): # Increase bit position bitpos += 1 # Divide by 2 to shift bits # in right at each step x //= 2 # Count of pairs for index i # till its set bit position for j in range(bitpos + 1): count += set_bits[j] # Increasing count of set bit # position of current element set_bits[bitpos] += 1 # Print the answer print (count) # Driver Code if __name__ == '__main__': arr = [4, 16, 8, 64] N = len(arr) # Function Call numberOfPairs(arr, N) # This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
class GFG
{
// Function to count the number of
// pairs as per the given conditions
static void numberOfPairs(int[] arr, int N)
{
// Initialize array set_bits as 0
int []set_bits = new int[31];
for (int i = 0; i < N; i++)
{
set_bits[i] = 0;
}
// Store the total number of
// required pairs
int count = 0;
// Traverse the array arr[]
for (int i = 0; i < N; i++)
{
// Store arr[i] in x
int x = arr[i];
// Store the position of the
// leftmost set bit in arr[i]
int bitpos = -1;
while (x > 0)
{
// Increase bit position
bitpos++;
// Divide by 2 to shift bits
// in right at each step
x /= 2;
}
// Count of pairs for index i
// till its set bit position
for (int j = 0;
j <= bitpos; j++)
{
count += set_bits[j];
}
// Increasing count of set bit
// position of current element
set_bits[bitpos]++;
}
// Print the answer
Console.Write(count);
}
// Driver Code
static public void Main()
{
int[] arr = { 4, 16, 8, 64 };
int N = arr.Length;
// Function Call
numberOfPairs(arr, N);
}
}
// This code is contributed by splevel62.
Javascript
<script>
// Javascript program for the above approach
// Function to count the number of
// pairs as per the given conditions
function numberOfPairs(arr, N)
{
// Initialize array set_bits as 0
let set_bits = [];
for (let i = 0; i < 31; i++)
{
set_bits[i] = 0;
}
// Store the total number of
// required pairs
let count = 0;
// Traverse the array arr[]
for (let i = 0; i < N; i++)
{
// Store arr[i] in x
let x = arr[i];
// Store the position of the
// leftmost set bit in arr[i]
let bitpos = -1;
while (x > 0)
{
// Increase bit position
bitpos++;
// Divide by 2 to shift bits
// in right at each step
x = Math.floor( x / 2 );
}
// Count of pairs for index i
// till its set bit position
for (let j = 0;
j <= bitpos; j++)
{
count += set_bits[j];
}
// Increasing count of set bit
// position of current element
set_bits[bitpos]++;
}
// Print the answer
document.write(count);
}
// Driver Code
let arr = [ 4, 16, 8, 64 ];
let N = arr.length;
// Function Call
numberOfPairs(arr, N);
</script>
5
Complejidad de tiempo: O(N*log M), donde M es el elemento más grande de la array .
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por shubhampokhriyal2018 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA