Dada una array arr[] de N enteros, la tarea es encontrar el número de pares no ordenados (i, j) en la array tal que la proporción de elementos en estos índices sea la misma que la proporción de índices ( arr[j] /arr[i] = j/i ).
Ejemplos:
Entrada: arr[] = {4, 5, 12, 10, 6}
Salida: 2
Explicación: Los pares que siguen la condición dada son:
- (1, 3) como arr[3] / arr[1] = 12/4 = 3 = 3/1
- (2, 4) como arr[4] / arr[2] = 10/5 = 2 = 4/2
Entrada: arr[] = {5, -2, 4, 20, 25, -6}
Salida: 3
Enfoque ingenuo : el problema dado se puede resolver iterando sobre todos los pares no ordenados (i, j) en la array dada mientras se realiza un seguimiento del número de pares que siguen la condición arr[j] / arr[i] = j / i .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function of find the count of unordered
// pairs (i, j) in the array such that
// arr[j] / arr[i] = j / i.
int countPairs(int arr[], int n)
{
// Stores the count of valid pairs
int count = 0;
// Iterating over all possible pairs
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
// Check if the pair is valid
if ((arr[j] % arr[i] == 0)
&& (j + 1) % (i + 1) == 0
&& (arr[j] / arr[i]
== (j + 1) / (i + 1))) {
count++;
}
}
}
// Return answer
return count;
}
// Driver Code
int main()
{
int arr[] = { 5, -2, 4, 20, 25, -6 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function Call
cout << countPairs(arr, n);
return 0;
}
Java
// Java program of the above approach
import java.util.*;
class GFG
{
// Function of find the count of unordered
// pairs (i, j) in the array such that
// arr[j] / arr[i] = j / i.
static int countPairs(int arr[], int n)
{
// Stores the count of valid pairs
int count = 0;
// Iterating over all possible pairs
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
// Check if the pair is valid
if ((arr[j] % arr[i] == 0)
&& (j + 1) % (i + 1) == 0
&& (arr[j] / arr[i]
== (j + 1) / (i + 1))) {
count++;
}
}
}
// Return answer
return count;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 5, -2, 4, 20, 25, -6 };
int n = arr.length;
// Function Call
System.out.print(countPairs(arr, n));
}
}
// This code is contributed by shikhasingrajput
Python3
# Python 3 program of the above approach # Function of find the count of unordered # pairs (i, j) in the array such that # arr[j] / arr[i] = j / i. def countPairs(arr, n): # Stores the count of valid pairs count = 0 # Iterating over all possible pairs for i in range(n - 1): for j in range(i + 1, n): # Check if the pair is valid if ((arr[j] % arr[i] == 0) and (j + 1) % (i + 1) == 0 and (arr[j] // arr[i] == (j + 1) // (i + 1))): count += 1 # Return answer return count # Driver Code if __name__ == "__main__": arr = [5, -2, 4, 20, 25, -6] n = len(arr) # Function Call print(countPairs(arr, n)) # This code is contributed by ukasp.
C#
// C# program for the above approach
using System;
public class GFG
{
// Function of find the count of unordered
// pairs (i, j) in the array such that
// arr[j] / arr[i] = j / i.
static int countPairs(int[] arr, int n)
{
// Stores the count of valid pairs
int count = 0;
// Iterating over all possible pairs
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
// Check if the pair is valid
if ((arr[j] % arr[i] == 0)
&& (j + 1) % (i + 1) == 0
&& (arr[j] / arr[i]
== (j + 1) / (i + 1))) {
count++;
}
}
}
// Return answer
return count;
}
// Driver Code
public static void Main (string[] args)
{
int[] arr = { 5, -2, 4, 20, 25, -6 };
int n = arr.Length;
// Function Call
Console.WriteLine(countPairs(arr, n));
}
}
// This code is contributed by avijitmondal1998.
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function of find the count of unordered
// pairs (i, j) in the array such that
// arr[j] / arr[i] = j / i.
function countPairs(arr, n)
{
// Stores the count of valid pairs
let count = 0;
// Iterating over all possible pairs
for (let i = 0; i < n - 1; i++) {
for (let j = i + 1; j < n; j++) {
// Check if the pair is valid
if ((arr[j] % arr[i] == 0)
&& (j + 1) % (i + 1) == 0
&& (arr[j] / arr[i]
== (j + 1) / (i + 1))) {
count++;
}
}
}
// Return answer
return count;
}
// Driver Code
let arr = [5, -2, 4, 20, 25, -6];
let n = arr.length;
// Function Call
document.write(countPairs(arr, n));
// This code is contributed by Potta Lokesh
</script>
Producción
3
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar utilizando la observación de que el valor máximo de y / x para cualquier par (x, y) que se puede alcanzar es N . Además, y debe ser divisible por x . Por lo tanto, para x en el rango [1, N] , itere sobre todo y en el rango [1, N] de manera que y sea divisible por x y mantenga un registro del número de pares (x, y) de tal manera que arr[ y] / arreglo[x] = y / x . Esto se puede hacer usando el Tamiz de Eratóstenes .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function of find the count of unordered
// pairs (i, j) in the array such that
// arr[j] / arr[i] = j / i.
int countPairs(int arr[], int n)
{
// Stores the count of valid pairs
int count = 0;
// Iterating over all values of
// x in range [1, N].
for (int x = 1; x <= n; x++) {
// Iterating over all values
// of y that are divisible by
// x in the range [1, N].
for (int y = 2 * x; y <= n; y += x) {
// Check if the pair is valid
if ((arr[y - 1] % arr[x - 1] == 0)
&& (arr[y - 1] / arr[x - 1]
== y / x)) {
count++;
}
}
}
// Return answer
return count;
}
// Driver Code
int main()
{
int arr[] = { 5, -2, 4, 20, 25, -6 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function Call
cout << countPairs(arr, n);
return 0;
}
Java
// Java program of the above approach
class GFG{
// Function of find the count of unordered
// pairs (i, j) in the array such that
// arr[j] / arr[i] = j / i.
static int countPairs(int arr[], int n)
{
// Stores the count of valid pairs
int count = 0;
// Iterating over all values of
// x in range [1, N].
for (int x = 1; x <= n; x++) {
// Iterating over all values
// of y that are divisible by
// x in the range [1, N].
for (int y = 2 * x; y <= n; y += x) {
// Check if the pair is valid
if ((arr[y - 1] % arr[x - 1] == 0)
&& (arr[y - 1] / arr[x - 1]
== y / x)) {
count++;
}
}
}
// Return answer
return count;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 5, -2, 4, 20, 25, -6 };
int n = arr.length;
// Function Call
System.out.print(countPairs(arr, n));
}
}
// This code is contributed by shikhasingrajput
Python3
# Python 3 program of the above approach # Function of find the count of unordered # pairs (i, j) in the array such that # arr[j] / arr[i] = j / i. def countPairs(arr, n): # Stores the count of valid pairs count = 0 # Iterating over all values of # x in range [1, N]. for x in range(1, n + 1, 1): # Iterating over all values # of y that are divisible by # x in the range [1, N]. for y in range(2 * x, n + 1, x): # Check if the pair is valid if ((arr[y - 1] % arr[x - 1] == 0) and (arr[y - 1] // arr[x - 1] == y // x)): count += 1 # Return answer return count # Driver Code if __name__ == '__main__': arr = [5, -2, 4, 20, 25, -6] n = len(arr) # Function Call print(countPairs(arr, n)) # This code is contributed by SURENDRA_GANGWAR.
C#
// C# program of the above approach
using System;
class GFG {
// Function of find the count of unordered
// pairs (i, j) in the array such that
// arr[j] / arr[i] = j / i.
static int countPairs(int[] arr, int n)
{
// Stores the count of valid pairs
int count = 0;
// Iterating over all values of
// x in range [1, N].
for (int x = 1; x <= n; x++) {
// Iterating over all values
// of y that are divisible by
// x in the range [1, N].
for (int y = 2 * x; y <= n; y += x) {
// Check if the pair is valid
if ((arr[y - 1] % arr[x - 1] == 0)
&& (arr[y - 1] / arr[x - 1] == y / x)) {
count++;
}
}
}
// Return answer
return count;
}
// Driver Code
public static void Main()
{
int[] arr = { 5, -2, 4, 20, 25, -6 };
int n = arr.Length;
// Function Call
Console.WriteLine(countPairs(arr, n));
}
}
// This code is contributed by ukasp.
Javascript
<script>
// javascript program of the above approach
// Function of find the count of unordered
// pairs (i, j) in the array such that
// arr[j] / arr[i] = j / i.
function countPairs(arr , n)
{
// Stores the count of valid pairs
var count = 0;
// Iterating over all values of
// x in range [1, N].
for (var x = 1; x <= n; x++) {
// Iterating over all values
// of y that are divisible by
// x in the range [1, N].
for (var y = 2 * x; y <= n; y += x) {
// Check if the pair is valid
if ((arr[y - 1] % arr[x - 1] == 0)
&& (arr[y - 1] / arr[x - 1]
== y / x)) {
count++;
}
}
}
// Return answer
return count;
}
// Driver Code
var arr = [ 5, -2, 4, 20, 25, -6 ];
var n = arr.length;
// Function Call
document.write(countPairs(arr, n));
// This code is contributed by shikhasingrajput
</script>
Producción
3
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por subhankarjadab y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA