Dada una array arr[] de longitud N con enteros distintos de 1 a 2*N, la tarea es contar el número de pares de índices (i, j) tales que (i < j) y arr[i] * arr[ j] = i + j , es decir, calcular el número de pares tal que su producto sea igual a su suma de índices.
Ejemplos:
Entrada: N = 5, arr[] = {3, 1, 5, 9, 2}
Salida: 3
Explicación: Hay tres pares (i, j) tales que (i < j) y arr[i] * arr[ j] = yo + j (1, 2), (1, 5), (2, 3)Entrada: N = 3, arr[] = {6, 1, 5}
Salida: 1
Enfoque ingenuo: iterar sobre todos los pares de índices (i, j) con (i < j) y verificar para cada par si se cumple la condición anterior, luego aumentar la respuesta en 1; de lo contrario, pasar al siguiente par.
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 the number of
// unique pairs
int NumberOfRequiredPairs(int arr[], int N)
{
// Variable that with stores number
// of valid pairs
int ans = 0;
// Traverse the array for every
// possible index i
for (int i = 0; i < N; i++)
// Traverse the array for every
// possible j (i < j)
// Please note that the indices
// are used as 1 based indexing
for (int j = i + 1; j < N; j++)
if ((arr[i] * arr[j])
== ((i + 1) + (j + 1)))
ans++;
// Return the ans
return ans;
}
// Driver Code
int main()
{
// Given Input
int N = 5;
int arr[] = { 3, 1, 5, 9, 2 };
// Function Call
cout << NumberOfRequiredPairs(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG
{
// Function to find the number of
// unique pairs
static int NumberOfRequiredPairs(int arr[], int N)
{
// Variable that with stores number
// of valid pairs
int ans = 0;
// Traverse the array for every
// possible index i
for (int i = 0; i < N; i++)
// Traverse the array for every
// possible j (i < j)
// Please note that the indices
// are used as 1 based indexing
for (int j = i + 1; j < N; j++)
if ((arr[i] * arr[j])
== ((i + 1) + (j + 1)))
ans++;
// Return the ans
return ans;
}
// Driver code
public static void main (String[] args)
{
// Given Input
int N = 5;
int arr[] = { 3, 1, 5, 9, 2 };
// Function Call
System.out.println(NumberOfRequiredPairs(arr, N));
}
}
// This code is contributed by sanjoy_62.
Python3
# Python program for the above approach # Function to find the number of # unique pairs def NumberOfRequiredPairs(arr, N): # Variable that with stores number # of valid pairs ans = 0 # Traverse the array for every # possible index i for i in range(N): # Traverse the array for every # possible j (i < j) # Please note that the indices # are used as 1 based indexing for j in range(i + 1, N): if ((arr[i] * arr[j]) == ((i + 1) + (j + 1))): ans += 1 # Return the ans return ans # Driver Code # Given Input N = 5 arr = [3, 1, 5, 9, 2] # Function Call print(NumberOfRequiredPairs(arr, N)) # This code is contributed by Saurabh Jaiswal
C#
// C# program for the above approach
using System;
class GFG
{
// Function to find the number of
// unique pairs
static int NumberOfRequiredPairs(int []arr, int N)
{
// Variable that with stores number
// of valid pairs
int ans = 0;
// Traverse the array for every
// possible index i
for (int i = 0; i < N; i++)
// Traverse the array for every
// possible j (i < j)
// Please note that the indices
// are used as 1 based indexing
for (int j = i + 1; j < N; j++)
if ((arr[i] * arr[j])
== ((i + 1) + (j + 1)))
ans++;
// Return the ans
return ans;
}
// Driver code
public static void Main ()
{
// Given Input
int N = 5;
int []arr = { 3, 1, 5, 9, 2 };
// Function Call
Console.Write(NumberOfRequiredPairs(arr, N));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// Javascript program for the above approach
// Function to find the number of
// unique pairs
function NumberOfRequiredPairs(arr, N)
{
// Variable that with stores number
// of valid pairs
let ans = 0;
// Traverse the array for every
// possible index i
for (let i = 0; i < N; i++)
// Traverse the array for every
// possible j (i < j)
// Please note that the indices
// are used as 1 based indexing
for (let j = i + 1; j < N; j++)
if ((arr[i] * arr[j])
== ((i + 1) + (j + 1)))
ans++;
// Return the ans
return ans;
}
// Driver Code
// Given Input
let N = 5;
let arr = [ 3, 1, 5, 9, 2 ];
// Function Call
document.write(NumberOfRequiredPairs(arr, N));
// This code is contributed by Samim Hossain Mondal.
</script>
Producción
3
Complejidad de tiempo: O(N^2)
Espacio auxiliar: O(1)
Enfoque eficiente: reescriba la condición mencionada como
array[j] = (i + j)/arr[i]
Por lo tanto, para cada múltiplo de arr[i], encuentre el respectivo j y verifique si arr[j] es igual a (i + j)/ arr[i]. Este enfoque es eficiente porque para cada i se requiere pasar por cada múltiplo de i hasta 2*N . Como todos los números en la array son distintos , se puede concluir que el total de iteraciones para calcular j será como:
N + N/2 + N/3 + N/4 + N/5……
Este es un resultado bien conocido de la serie de expansiones de logN . Para obtener más información, lea sobre esto aquí . Siga los pasos a continuación para resolver el problema:
- Inicialice la variable ans como 0 para almacenar la respuesta.
- Iterar sobre el rango [0, N] usando la variable i y realizar los siguientes pasos:
- Inicialice la variable k como el valor de arr[i].
- Iterar en un ciclo while hasta que k sea menor que 2*N y realizar las siguientes tareas:
- Inicialice la variable j como ki-1.
- Si j es mayor que igual a 1 y menor que igual a N y arr[j – 1] es igual a k / arr[i] y j es mayor que i+1, entonces aumente el valor de ans en 1.
- Después de realizar los pasos anteriores, imprima el valor de ans como respuesta.
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 the number of
// unique pairs
int NumberOfRequiredPairs(int arr[], int N)
{
// Variable that with stores
// number of valid pairs
int ans = 0;
// Traverse the array for every
// possible index i
for (int i = 0; i < N; i++) {
// Initialize a dummy variable
// for arr[i]
int k = arr[i];
// We will loop through every
// multiple of arr[i];
// Looping through 2*N because
// the maximum element
// in array can be 2*N
// Please not that i and j are
// in 1 based indexing
while (k <= 2 * N) {
// Calculating j
int j = k - i - 1;
// Now check if this j lies
// between the bounds
// of the array
if (j >= 1 && j <= N) {
// Checking the required
// condition
if ((arr[j - 1] == k / arr[i])
&& j > i + 1) {
ans++;
}
}
// Increasing k to its next multiple
k += arr[i];
}
}
// Return the ans
return ans;
}
// Driver Code
int main()
{
// Given Input
int N = 5;
int arr[] = { 3, 1, 5, 9, 2 };
// Function Call
cout << NumberOfRequiredPairs(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
public class GFG
{
// Function to find the number of
// unique pairs
static int NumberOfRequiredPairs(int arr[], int N)
{
// Variable that with stores
// number of valid pairs
int ans = 0;
// Traverse the array for every
// possible index i
for (int i = 0; i < N; i++) {
// Initialize a dummy variable
// for arr[i]
int k = arr[i];
// We will loop through every
// multiple of arr[i];
// Looping through 2*N because
// the maximum element
// in array can be 2*N
// Please not that i and j are
// in 1 based indexing
while (k <= 2 * N) {
// Calculating j
int j = k - i - 1;
// Now check if this j lies
// between the bounds
// of the array
if (j >= 1 && j <= N) {
// Checking the required
// condition
if ((arr[j - 1] == k / arr[i])
&& j > i + 1) {
ans++;
}
}
// Increasing k to its next multiple
k += arr[i];
}
}
// Return the ans
return ans;
}
// Driver code
public static void main (String args[])
{
// Given Input
int N = 5;
int arr[] = { 3, 1, 5, 9, 2 };
// Function Call
System.out.println(NumberOfRequiredPairs(arr, N));
}
}
// This code is contributed by Samim Hossain Mondal.
Python3
# Python3 program for the above approach # Function to find the number of # unique pairs def NumberOfRequiredPairs(arr, N) : # Variable that with stores # number of valid pairs ans = 0; # Traverse the array for every # possible index i for i in range(N) : # Initialize a dummy variable # for arr[i] k = arr[i]; # We will loop through every # multiple of arr[i]; # Looping through 2*N because # the maximum element # in array can be 2*N # Please not that i and j are # in 1 based indexing while (k <= 2 * N) : # Calculating j j = k - i - 1; # Now check if this j lies # between the bounds # of the array if (j >= 1 and j <= N) : # Checking the required # condition if ((arr[j - 1] == k // arr[i]) and j > i + 1) : ans += 1; # Increasing k to its next multiple k += arr[i]; # Return the ans return ans; # Driver Code if __name__ == "__main__" : # Given Input N = 5; arr = [ 3, 1, 5, 9, 2 ]; # Function Call print(NumberOfRequiredPairs(arr, N)); # This code is contributed by AnkThon
C#
// C# program for the above approach
using System;
class GFG
{
// Function to find the number of
// unique pairs
static int NumberOfRequiredPairs(int []arr, int N)
{
// Variable that with stores
// number of valid pairs
int ans = 0;
// Traverse the array for every
// possible index i
for (int i = 0; i < N; i++) {
// Initialize a dummy variable
// for arr[i]
int k = arr[i];
// We will loop through every
// multiple of arr[i];
// Looping through 2*N because
// the maximum element
// in array can be 2*N
// Please not that i and j are
// in 1 based indexing
while (k <= 2 * N) {
// Calculating j
int j = k - i - 1;
// Now check if this j lies
// between the bounds
// of the array
if (j >= 1 && j <= N) {
// Checking the required
// condition
if ((arr[j - 1] == k / arr[i])
&& j > i + 1) {
ans++;
}
}
// Increasing k to its next multiple
k += arr[i];
}
}
// Return the ans
return ans;
}
// Driver code
public static void Main ()
{
// Given Input
int N = 5;
int []arr = { 3, 1, 5, 9, 2 };
// Function Call
Console.Write(NumberOfRequiredPairs(arr, N));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// Javascript program for the above approach
// Function to find the number of
// unique pairs
function NumberOfRequiredPairs(arr, N)
{
// Variable that with stores
// number of valid pairs
let ans = 0;
// Traverse the array for every
// possible index i
for (let i = 0; i < N; i++) {
// Initialize a dummy variable
// for arr[i]
let k = arr[i];
// We will loop through every
// multiple of arr[i];
// Looping through 2*N because
// the maximum element
// in array can be 2*N
// Please not that i and j are
// in 1 based indexing
while (k <= 2 * N) {
// Calculating j
let j = k - i - 1;
// Now check if this j lies
// between the bounds
// of the array
if (j >= 1 && j <= N) {
// Checking the required
// condition
if ((arr[j - 1] == k / arr[i])
&& j > i + 1) {
ans++;
}
}
// Increasing k to its next multiple
k += arr[i];
}
}
// Return the ans
return ans;
}
// Driver Code
// Given Input
let N = 5;
let arr = [ 3, 1, 5, 9, 2 ];
// Function Call
document.write(NumberOfRequiredPairs(arr, N));
// This code is contributed by Samim Hossain Mondal.
</script>
Producción
3
Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA