Dada una array de enteros arr[0..n-1], cuente todos los pares (arr[i], arr[j]) de tal manera que i*arr[i] > j*arr[j], 0 =< yo < j < n.
Ejemplos:
Input : arr[] = {5 , 0, 10, 2, 4, 1, 6}
Output: 5
Pairs which hold condition i*arr[i] > j*arr[j]
are (10, 2) (10, 4) (10, 1) (2, 1) (4, 1)
Input : arr[] = {8, 4, 2, 1}
Output : 2
Una solución simple es ejecutar dos bucles. Elija cada elemento de la array uno por uno y para cada elemento busque un elemento en el lado derecho de la array que contenga la condición, luego incremente el contador y, por último, devuelva el valor del contador.
A continuación se muestra la implementación de la idea anterior:
C++
// C++ program to count all pair that
// hold condition i*arr[i] > j*arr[j]
#include<iostream>
using namespace std;
// Return count of pair in given array
// such that i*arr[i] > j*arr[j]
int CountPair(int arr[] , int n )
{
int result = 0; // Initialize result
for (int i=0; i<n; i++)
{
// Generate all pair and increment
// counter if the hold given condition
for (int j = i + 1; j < n; j++)
if (i*arr[i] > j*arr[j] )
result ++;
}
return result;
}
// Driver code
int main()
{
int arr[] = {5 , 0, 10, 2, 4, 1, 6} ;
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Count of Pairs : "
<< CountPair(arr, n);
return 0;
}
Java
// Java Code for Count pairs in an
// array that hold i*arr[i] > j*arr[j]
class GFG {
// Return count of pair in given array
// such that i*arr[i] > j*arr[j]
public static int CountPair(int arr[] , int n )
{
int result = 0; // Initialize result
for (int i = 0; i < n; i++)
{
// Generate all pair and increment
// counter if the hold given condition
for (int j = i + 1; j < n; j++)
if (i*arr[i] > j*arr[j] )
result ++;
}
return result;
}
/* Driver program to test above function */
public static void main(String[] args)
{
int arr[] = {5 , 0, 10, 2, 4, 1, 6} ;
int n = arr.length;
System.out.println("Count of Pairs : " +
CountPair(arr, n));
}
}
// This code is contributed by Arnav Kr. Mandal.
Python3
# Python3 Code to Count pairs in an
# array that hold i*arr[i] > j*arr[j]
# Return count of pair in given array
# such that i*arr[i] > j*arr[j]
def CountPair(arr , n ):
# Initialize result
result = 0;
for i in range (0, n):
# Generate all pair and increment
# counter if the hold given condition
j = i + 1
while(j < n):
if (i * arr[i] > j * arr[j] ):
result = result +1
j = j + 1
return result;
# Driver program to test above function */
arr = [5, 0, 10, 2, 4, 1, 6]
n = len(arr)
print("Count of Pairs : " , CountPair(arr, n))
# This code is contributed by Sam007.
C#
// C# Code to Count pairs in an
// array that hold i*arr[i] > j*arr[j]
using System;
class GFG
{
// Return count of pair in given array
// such that i*arr[i] > j*arr[j]
public static int CountPair(int []arr , int n )
{
// Initialize result
int result = 0;
for (int i = 0; i < n; i++)
{
// Generate all pair and increment
// counter if the hold given condition
for (int j = i + 1; j < n; j++)
if (i*arr[i] > j*arr[j] )
result ++;
}
return result;
}
/* Driver program to test above function */
public static void Main()
{
int []arr = {5, 0, 10, 2, 4, 1, 6};
int n = arr.Length;
Console.WriteLine("Count of Pairs : " +
CountPair(arr, n));
}
}
// This code is contributed by Sam007
PHP
<?php
// PHP program to count all pair that
// hold condition i*arr[i] > j*arr[j]
// Return count of pair in given array
// such that i*arr[i] > j*arr[j]
function CountPair($arr , $n )
{
// Initialize result
$result = 0;
for($i = 0; $i < $n; $i++)
{
// Generate all pair and increment
// counter if the hold given condition
for ($j = $i + 1; $j < $n; $j++)
if ($i * $arr[$i] > $j * $arr[$j] )
$result ++;
}
return $result;
}
// Driver code
$arr = array(5, 0, 10, 2, 4, 1, 6) ;
$n = sizeof($arr);
echo "Count of Pairs : ",
CountPair($arr, $n);
// This code is contributed by m_kit
?>
Javascript
<script>
// JavaScript program to Count pairs in an
// array that hold i*arr[i] > j*arr[j]
// Return count of pair in given array
// such that i*arr[i] > j*arr[j]
function CountPair(arr, n)
{
// Initialize result
let result = 0;
for(let i = 0; i < n; i++)
{
// Generate all pair and increment
// counter if the hold given condition
for(let j = i + 1; j < n; j++)
if (i * arr[i] > j * arr[j] )
result ++;
}
return result;
}
// Driver Code
let arr = [5 , 0, 10, 2, 4, 1, 6] ;
let n = arr.length;
document.write("Count of Pairs : " +
CountPair(arr, n));
// This code is contributed by souravghosh0416
</script>
Producción
Count of Pairs : 5
Tiempo Complejidad: O(n 2 )
Espacio Auxiliar: O(1)
Una solución eficiente a este problema requiere un tiempo O(n log n). La idea se basa en un hecho interesante sobre este problema después de modificar la array de modo que cada elemento se multiplique por su índice, este problema se convierte en Count Inversions en una array .
Algoritmo:
Dada una array ‘arr’ y su tamaño ‘n’
- Primer elemento de array transversal, va de 0 a n-1
- Multiplica cada elemento con su índice arr[i] = arr[i] * i
- Después de ese paso 1, todo el proceso es similar a Contar inversiones en una array .
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to count all pair that
// hold condition i*arr[i] > j*arr[j]
#include <bits/stdc++.h>
using namespace std;
/* This function merges two sorted arrays and
returns inversion count in the arrays.*/
int merge(int arr[], int temp[], int left,
int mid, int right)
{
int inv_count = 0;
int i = left; /* index for left subarray*/
int j = mid; /* index for right subarray*/
int k = left; /* index for resultant subarray*/
while ((i <= mid - 1) && (j <= right))
{
if (arr[i] <= arr[j])
temp[k++] = arr[i++];
else
{
temp[k++] = arr[j++];
inv_count = inv_count + (mid - i);
}
}
/* Copy the remaining elements of left
subarray (if there are any) to temp*/
while (i <= mid - 1)
temp[k++] = arr[i++];
/* Copy the remaining elements of right
subarray (if there are any) to temp*/
while (j <= right)
temp[k++] = arr[j++];
/* Copy back the merged elements to original
array*/
for (i=left; i <= right; i++)
arr[i] = temp[i];
return inv_count;
}
/* An auxiliary recursive function that sorts
the input array and returns the number of
inversions in the array. */
int _mergeSort(int arr[], int temp[], int left,
int right)
{
int mid, inv_count = 0;
if (right > left)
{
/* Divide the array into two parts and call
_mergeSortAndCountInv() for each of
the parts */
mid = (right + left)/2;
/* Inversion count will be sum of inversions in
left-part, right-part and number of inversions
in merging */
inv_count = _mergeSort(arr, temp, left, mid);
inv_count += _mergeSort(arr, temp, mid+1, right);
/*Merge the two parts*/
inv_count += merge(arr, temp, left, mid+1, right);
}
return inv_count;
}
/* This function sorts the input array and
returns the number of inversions in the
array */
int countPairs(int arr[], int n)
{
// Modify the array so that problem reduces to
// count inversion problem.
for (int i=0; i<n; i++)
arr[i] = i*arr[i];
// Count inversions using same logic as
// below post
// https://www.geeksforgeeks.org/counting-inversions/
int temp[n];
return _mergeSort(arr, temp, 0, n - 1);
}
// Driver code
int main()
{
int arr[] = {5, 0, 10, 2, 4, 1, 6};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Count of Pairs : "
<< countPairs(arr, n);
return 0;
}
Java
// Java program to count all pair that
// hold condition i*arr[i] > j*arr[j]
import java.io.*;
class GFG
{
// This function merges two sorted arrays and
// returns inversion count in the arrays.
static int merge(int arr[], int temp[], int left,
int mid, int right)
{
int inv_count = 0;
/* index for left subarray*/
int i = left;
/* index for right subarray*/
int j = mid;
/* index for resultant subarray*/
int k = left;
while ((i <= mid - 1) && (j <= right))
{
if (arr[i] <= arr[j])
temp[k++] = arr[i++];
else
{
temp[k++] = arr[j++];
inv_count = inv_count + (mid - i);
}
}
/* Copy the remaining elements of left
subarray (if there are any) to temp*/
while (i <= mid - 1)
temp[k++] = arr[i++];
/* Copy the remaining elements of right
subarray (if there are any) to temp*/
while (j <= right)
temp[k++] = arr[j++];
// Copy back the merged elements
// to original array
for (i = left; i <= right; i++)
arr[i] = temp[i];
return inv_count;
}
/* An auxiliary recursive function
that sorts the input array and
returns the number of inversions
in the array. */
static int _mergeSort(int arr[], int temp[],
int left,int right)
{
int mid, inv_count = 0;
if (right > left)
{
/* Divide the array into two parts and call
_mergeSortAndCountInv() for each of
the parts */
mid = (right + left) / 2;
// Inversion count will be sum of inversions in
// left-part, right-part and number of inversions
// in merging
inv_count = _mergeSort(arr, temp, left, mid);
inv_count += _mergeSort(arr, temp, mid+1, right);
/*Merge the two parts*/
inv_count += merge(arr, temp, left, mid+1, right);
}
return inv_count;
}
// This function sorts the input array and
// returns the number of inversions in the
// array
static int countPairs(int arr[], int n)
{
// Modify the array so that problem reduces to
// count inversion problem.
for (int i = 0; i < n; i++)
arr[i] = i * arr[i];
// Count inversions using same logic as
// below post
// https://www.geeksforgeeks.org/counting-inversions/
int temp[] = new int [n];
return _mergeSort(arr, temp, 0, n - 1);
}
// Driver code
public static void main (String[] args)
{
int arr[] = {5, 0, 10, 2, 4, 1, 6};
int n = arr.length;
System.out.print( "Count of Pairs : "
+ countPairs(arr, n));
}
}
// This code is contributed by vt_m
Python3
# Python 3 program to count all
# pair that hold condition
# i*arr[i] > j*arr[j]
# This function merges two
# sorted arrays and returns
# inversion count in the arrays.
def merge(arr, temp, left, mid, right):
inv_count = 0
i = left # index for left subarray
j = mid # index for right subarray
k = left # index for resultant subarray
while ((i <= mid - 1) and (j <= right)):
if (arr[i] <= arr[j]):
temp[k] = arr[i]
i += 1
k += 1
else:
temp[k] = arr[j]
k += 1
j += 1
inv_count = inv_count + (mid - i)
# Copy the remaining elements of left
# subarray (if there are any) to temp
while (i <= mid - 1):
temp[k] = arr[i]
i += 1
k += 1
# Copy the remaining elements of right
# subarray (if there are any) to temp
while (j <= right):
temp[k] = arr[j]
k += 1
j += 1
# Copy back the merged elements
# to original array
for i in range(left, right + 1):
arr[i] = temp[i]
return inv_count
# An auxiliary recursive function
# that sorts the input array and
# returns the number of inversions
# in the array.
def _mergeSort(arr, temp, left, right):
inv_count = 0
if (right > left):
# Divide the array into two parts
# and call _mergeSortAndCountInv()
# for each of the parts
mid = (right + left) // 2
# Inversion count will be sum of
# inversions in left-part, right-part x
# and number of inversions in merging
inv_count = _mergeSort(arr, temp, left, mid)
inv_count += _mergeSort(arr, temp,
mid + 1, right)
# Merge the two parts
inv_count += merge(arr, temp, left,
mid + 1, right)
return inv_count
# This function sorts the input
# array and returns the number
# of inversions in the array
def countPairs(arr, n):
# Modify the array so that problem
# reduces to count inversion problem.
for i in range(n):
arr[i] = i * arr[i]
# Count inversions using same
# logic as below post
# https://www.geeksforgeeks.org/counting-inversions/
temp = [0] * n
return _mergeSort(arr, temp, 0, n - 1)
# Driver code
if __name__ == "__main__":
arr = [5, 0, 10, 2, 4, 1, 6]
n = len(arr)
print("Count of Pairs : ",
countPairs(arr, n))
# This code is contributed
# by ChitraNayal
C#
// C# program to count all pair that
// hold condition i*arr[i] > j*arr[j]
using System;
class GFG
{
// This function merges two sorted arrays and
// returns inversion count in the arrays.
static int merge(int []arr, int []temp, int left,
int mid, int right)
{
int inv_count = 0;
/* index for left subarray*/
int i = left;
/* index for right subarray*/
int j = mid;
/* index for resultant subarray*/
int k = left;
while ((i <= mid - 1) && (j <= right))
{
if (arr[i] <= arr[j])
temp[k++] = arr[i++];
else
{
temp[k++] = arr[j++];
inv_count = inv_count + (mid - i);
}
}
/* Copy the remaining elements of left
subarray (if there are any) to temp*/
while (i <= mid - 1)
temp[k++] = arr[i++];
/* Copy the remaining elements of right
subarray (if there are any) to temp*/
while (j <= right)
temp[k++] = arr[j++];
// Copy back the merged elements
// to original array
for (i = left; i <= right; i++)
arr[i] = temp[i];
return inv_count;
}
/* An auxiliary recursive function
that sorts the input array and
returns the number of inversions
in the array. */
static int _mergeSort(int []arr, int []temp,
int left,int right)
{
int mid, inv_count = 0;
if (right > left)
{
/* Divide the array into two parts and call
_mergeSortAndCountInv() for each of
the parts */
mid = (right + left) / 2;
// Inversion count will be sum of inversions in
// left-part, right-part and number of inversions
// in merging
inv_count = _mergeSort(arr, temp, left, mid);
inv_count += _mergeSort(arr, temp, mid+1, right);
/*Merge the two parts*/
inv_count += merge(arr, temp, left, mid+1, right);
}
return inv_count;
}
// This function sorts the input array and
// returns the number of inversions in the
// array
static int countPairs(int []arr, int n)
{
// Modify the array so that problem reduces to
// count inversion problem.
for (int i = 0; i < n; i++)
arr[i] = i * arr[i];
// Count inversions using same logic as
// below post
// https://www.geeksforgeeks.org/counting-inversions/
int []temp = new int [n];
return _mergeSort(arr, temp, 0, n - 1);
}
// Driver code
public static void Main ()
{
int []arr = {5, 0, 10, 2, 4, 1, 6};
int n = arr.Length;
Console.WriteLine( "Count of Pairs : "
+ countPairs(arr, n));
}
}
// This code is contributed by anuj_67.
Javascript
<script>
// Javascript program to count all pair that
// hold condition i*arr[i] > j*arr[j]
// This function merges two sorted arrays and
// returns inversion count in the arrays.
function merge(arr,temp,left,mid,right)
{
let inv_count = 0;
/* index for left subarray*/
let i = left;
/* index for right subarray*/
let j = mid;
/* index for resultant subarray*/
let k = left;
while ((i <= mid - 1) && (j <= right))
{
if (arr[i] <= arr[j])
temp[k++] = arr[i++];
else
{
temp[k++] = arr[j++];
inv_count = inv_count + (mid - i);
}
}
/* Copy the remaining elements of left
subarray (if there are any) to temp*/
while (i <= mid - 1)
temp[k++] = arr[i++];
/* Copy the remaining elements of right
subarray (if there are any) to temp*/
while (j <= right)
temp[k++] = arr[j++];
// Copy back the merged elements
// to original array
for (i = left; i <= right; i++)
arr[i] = temp[i];
return inv_count;
}
/* An auxiliary recursive function
that sorts the input array and
returns the number of inversions
in the array. */
function _mergeSort(arr,temp,left,right)
{
let mid, inv_count = 0;
if (right > left)
{
/* Divide the array into two parts and call
_mergeSortAndCountInv() for each of
the parts */
mid = Math.floor((right + left) / 2);
// Inversion count will be sum of inversions in
// left-part, right-part and number of inversions
// in merging
inv_count = _mergeSort(arr, temp, left, mid);
inv_count += _mergeSort(arr, temp, mid+1, right);
/*Merge the two parts*/
inv_count += merge(arr, temp, left, mid+1, right);
}
return inv_count;
}
// This function sorts the input array and
// returns the number of inversions in the
// array
function countPairs(arr,n)
{
// Modify the array so that problem reduces to
// count inversion problem.
for (let i = 0; i < n; i++)
arr[i] = i * arr[i];
// Count inversions using same logic as
// below post
// https://www.geeksforgeeks.org/counting-inversions/
let temp = new Array(n);
for(let i=0;i<temp;i++)
{
temp[i]=0;
}
return _mergeSort(arr, temp, 0, n - 1);
}
// Driver code
let arr=[5, 0, 10, 2, 4, 1, 6];
let n = arr.length;
document.write( "Count of Pairs : "
+ countPairs(arr, n));
// This code is contributed by rag2127
</script>
Producción
Count of Pairs : 5
Complejidad de Tiempo: O(n log n)
Espacio Auxiliar: O(n)
Otro enfoque eficiente (usando estructuras de datos basadas en políticas en C++ STL):
En este enfoque, primero almacenamos el valor i*arr[i] para cada índice i y le damos el nombre a esta array obtenida como una array modificada . Así que ahora en lugar de i*arr[i]>j*arr[j] en el arreglo original, tenemos que encontrar x>y donde x e y ahora son elementos del arreglo modificado donde el índice de x es más pequeño que el índice de y. En otras palabras, para cada índice i en la array modificada, el número total de dichos pares es el recuento de todos los elementos más pequeños a la derecha de ese índice.
Por lo tanto, el problema se transforma en otro problema en el que necesitamos encontrar el recuento de los elementos más pequeños del lado derecho para cada índice i en la array modificada.
Entonces, podemos resolver este problema de manera eficiente manteniendo una estructura de datos basada en políticas de pares.
Los pasos involucrados son:
- Recorre la array y para cada índice almaceno i*arr[i].
- Luego recorra la array modificada desde el final y cada vez que encontremos order_of_key del elemento actual para encontrar la cantidad de elementos más pequeños a la derecha.
- Luego agregaremos el valor obtenido de order_of_key del elemento actual a la variable ans.
- Después de eso, insertaremos el elemento actual en nuestra estructura de datos basada en políticas .
A continuación se muestra el código para el enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pbds \
tree<pair<int, int>, null_type, less<pair<int, int> >, \
rb_tree_tag, tree_order_statistics_node_update>
using namespace __gnu_pbds;
using namespace std;
// Print the count of pair in given array
// such that i*arr[i] > j*arr[j]
// for 0<=i<j<n
void countPrint(int arr[], int n)
{
// storing i*arr[i]
// for every index
for (int i=0;i<n;i++)
{
arr[i]=i*arr[i];
}
pbds s;
// variable to store the count
int ans=0;
for (int i = n - 1; i >= 0; i--) {
// for the last element count is
// zero so excluding it.
if(i!=n-1) {
// add the count of the smaller elements
// to the right of current element into
// the ans variable
ans+=s.order_of_key({ arr[i], i });
}
// insert current element
s.insert({ arr[i], i });
}
cout << ans << endl;
}
// Driver Code
int main()
{
int n = 7;
int arr[] = { 5 , 0, 10, 2, 4, 1, 6 };
countPrint(arr, n);
return 0;
}
// This code is contributed by Pushpesh raj
Producción
5
Complejidad de tiempo: O(n*log(n))
Espacio auxiliar: O(n)
Este artículo es una contribución de Nishant_Singh (Pintu) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA