Dada una array arr[] de tamaño N , la tarea es contar los posibles pares de elementos de la array (arr[i], arr[j]) tales que (arr[i] + arr[j]) * (arr[i] – arr[j]) es 1.
Ejemplos:
Entrada: arr[] = {3, 1, 1, 0}
Salida: 2
Explicación:
Los dos pares posibles son:
- (arr[1] + arr[3]) * (arr[1] – arr[3]) = 1
- (arr[2] + arr[3]) * (arr[2] – arr[3]) = 1
Entrada: arr[] = {12, 0, 1, 1, 14, 0, 9, 0}
Salida: 4
Explicación:
Los cuatro pares posibles son los siguientes:
- (3, 6): (arr[3] + arr[6]) * (arr[3] – arr[6]) = 1
- (4, 6): (arr[4] + arr[6]) * (arr[4] – arr[6]) = 1
- (3, 8): (arr[3] + arr[8]) * (arr[3] – arr[8]) = 1
- (3, 6): (arr[4] + arr[8]) * (arr[4] – arr[8]) = 1
Enfoque ingenuo: el enfoque más simple es atravesar la array y generar todos los pares posibles a partir de la array dada y contar aquellos pares cuyo producto de suma y diferencia es 1. Finalmente, imprima el recuento final obtenido después de completar los pasos anteriores.
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque eficiente: la condición dada se puede expresar para cualquier par de elementos de array (arr[i], arr[j]) como:
(arr[i] + arr[j]) * (arr[i] – arr[j]) = 1
=> (arr[i] 2 – arr[j] 2 ) = 1
Por lo tanto, se puede concluir que las condiciones requeridas solo pueden ser satisfechas por los pares arr[i] = 1 y arr[j] = 0 e i < j . Siga los pasos a continuación para resolver el problema:
- Inicialice dos variables, oneCount y wishPairs para almacenar el conteo de 1 y los pares requeridos respectivamente.
- Recorra la array dada y verifique lo siguiente:
- Si arr[i] = 1: Incremente oneCount en 1 .
- Si arr[i] = 0: Agregue el conteo de 1 s obtenido hasta ahora a los pares deseados .
- Después de completar los pasos anteriores, imprima el valor de los pares deseados como la respuesta requerida.
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 desired
// number of pairs
int countPairs(int arr[], int n)
{
// Initialize oneCount
int oneCount = 0;
// Initialize the desiredPair
int desiredPair = 0;
// Traverse the given array
for (int i = 0; i < n; i++) {
// If 1 is encountered
if (arr[i] == 1) {
oneCount++;
}
// If 0 is encountered
if (arr[i] == 0) {
// Update count of pairs
desiredPair += oneCount;
}
}
// Return the final count
return desiredPair;
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 3, 1, 1, 0 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
cout << countPairs(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG{
// Function to count the desired
// number of pairs
static int countPairs(int arr[], int n)
{
// Initialize oneCount
int oneCount = 0;
// Initialize the desiredPair
int desiredPair = 0;
// Traverse the given array
for(int i = 0; i < n; i++)
{
// If 1 is encountered
if (arr[i] == 1)
{
oneCount++;
}
// If 0 is encountered
if (arr[i] == 0)
{
// Update count of pairs
desiredPair += oneCount;
}
}
// Return the final count
return desiredPair;
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int arr[] = { 3, 1, 1, 0 };
int N = arr.length;
// Function call
System.out.println(countPairs(arr, N));
}
}
// This code is contributed by sanjoy_62
Python3
# Python3 program for the above approach # Function to count the desired # number of pairs def countPairs(arr, n): # Initialize oneCount oneCount = 0 # Initialize the desiredPair desiredPair = 0 # Traverse the given array for i in range(n): # If 1 is encountered if (arr[i] == 1): oneCount += 1 # If 0 is encountered if (arr[i] == 0): # Update count of pairs desiredPair += oneCount # Return the final count return desiredPair # Driver Code if __name__ == '__main__': # Given array arr[] arr = [ 3, 1, 1, 0 ] N = len(arr) # Function call print(countPairs(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 desired
// number of pairs
static int countPairs(int []arr, int n)
{
// Initialize oneCount
int oneCount = 0;
// Initialize the desiredPair
int desiredPair = 0;
// Traverse the given array
for(int i = 0; i < n; i++)
{
// If 1 is encountered
if (arr[i] == 1)
{
oneCount++;
}
// If 0 is encountered
if (arr[i] == 0)
{
// Update count of pairs
desiredPair += oneCount;
}
}
// Return the readonly count
return desiredPair;
}
// Driver Code
public static void Main(String[] args)
{
// Given array []arr
int []arr = { 3, 1, 1, 0 };
int N = arr.Length;
// Function call
Console.WriteLine(countPairs(arr, N));
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// Javascript program for the above approach
// Function to count the desired
// number of pairs
function countPairs(arr, n)
{
// Initialize oneCount
let oneCount = 0;
// Initialize the desiredPair
let desiredPair = 0;
// Traverse the given array
for(let i = 0; i < n; i++)
{
// If 1 is encountered
if (arr[i] == 1)
{
oneCount++;
}
// If 0 is encountered
if (arr[i] == 0)
{
// Update count of pairs
desiredPair += oneCount;
}
}
// Return the final count
return desiredPair;
}
// Driver Code
// Given array arr[]
let arr = [ 3, 1, 1, 0 ];
let N = arr.length;
// Function call
document.write(countPairs(arr, N));
// This code is contributed by target_2
</script>
2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)