Dada una array arr[] de longitud N y un entero K , la tarea es contar el número de pares (i, j) tales que i < j y arr[i] > K * arr[j] .
Ejemplos:
Entrada: arr[] = {5, 6, 2, 5}, K = 2
Salida: 2
Explicación: La array consta de dos de estos pares:
(5, 2): índice de 5 y 2 son 0, 2 respectivamente. Por lo tanto, se cumplen las condiciones requeridas (0 < 2 y 5 > 2 * 2).
(6, 2): Índice de 6 y 2 son 1, 2 respectivamente. Por lo tanto, se cumplen las condiciones requeridas (0 < 2 y 6 > 2 * 2).Entrada: arr[] = {4, 6, 5, 1}, K = 2
Salida: 3
Enfoque ingenuo: el enfoque más simple para resolver el problema es atravesar la array y, para cada índice, encontrar números que tengan índices mayores que él, de modo que el elemento en él cuando se multiplique por K sea menor que el elemento en el índice actual.
Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos cnt , con 0 para contar el número total de pares requeridos.
- Atraviesa la array de izquierda a derecha.
- Para cada índice posible, digamos i , atraviese los índices i + 1 a N – 1 y aumente el valor de cnt en 1 si se encuentra algún elemento, digamos arr[j], tal que arr[j] * K es menor que arr [yo] .
- Después de completar el recorrido de la array, imprima cnt como el conteo requerido de pares.
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 count required pairs
void getPairs(int arr[], int N, int K)
{
// Stores count of pairs
int count = 0;
// Traverse the array
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
// Check if the condition
// is satisfied or not
if (arr[i] > K * arr[j])
count++;
}
}
cout << count;
}
// Driver Code
int main()
{
int arr[] = { 5, 6, 2, 5 };
int N = sizeof(arr) / sizeof(arr[0]);
int K = 2;
// Function Call
getPairs(arr, N, K);
return 0;
}
Java
// Java program for the above approach
class GFG
{
// Function to find the count required pairs
static void getPairs(int arr[], int N, int K)
{
// Stores count of pairs
int count = 0;
// Traverse the array
for (int i = 0; i < N; i++)
{
for (int j = i + 1; j < N; j++)
{
// Check if the condition
// is satisfied or not
if (arr[i] > K * arr[j])
count++;
}
}
System.out.print(count);
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 5, 6, 2, 5 };
int N = arr.length;
int K = 2;
// Function Call
getPairs(arr, N, K);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach # Function to find the count required pairs def getPairs(arr, N, K): # Stores count of pairs count = 0 # Traverse the array for i in range(N): for j in range(i + 1, N): # Check if the condition # is satisfied or not if (arr[i] > K * arr[j]): count += 1 print(count) # Driver Code if __name__ == '__main__': arr = [ 5, 6, 2, 5 ] N = len(arr) K = 2 # Function Call getPairs(arr, N, K) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG
{
// Function to find the count required pairs
static void getPairs(int []arr, int N, int K)
{
// Stores count of pairs
int count = 0;
// Traverse the array
for (int i = 0; i < N; i++)
{
for (int j = i + 1; j < N; j++)
{
// Check if the condition
// is satisfied or not
if (arr[i] > K * arr[j])
count++;
}
}
Console.Write(count);
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 5, 6, 2, 5 };
int N = arr.Length;
int K = 2;
// Function Call
getPairs(arr, N, K);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript program for the above approach
// Function to find the count required pairs
function getPairs(arr, N, K)
{
// Stores count of pairs
let count = 0;
// Traverse the array
for(let i = 0; i < N; i++)
{
for(let j = i + 1; j < N; j++)
{
// Check if the condition
// is satisfied or not
if (arr[i] > K * arr[j])
count++;
}
}
document.write(count);
}
// Driver Code
let arr = [ 5, 6, 2, 5 ];
let N = arr.length;
let K = 2;
// Function Call
getPairs(arr, N, K);
// This code is contributed by splevel62
</script>
Producción
2
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque eficiente: la idea es utilizar el concepto de clasificación por combinación y luego contar los pares de acuerdo con las condiciones dadas. Siga los pasos a continuación para resolver el problema:
- Inicializa una variable, digamos answer , para contar el número de pares que satisfacen la condición dada.
- Divida repetidamente la array en dos mitades iguales o mitades casi iguales hasta que quede un elemento en cada partición.
- Llame a una función recursiva que cuente el número de veces que se cumple la condición arr[i] > K * arr[j] e i < j después de fusionar las dos particiones.
- Realícelo inicializando dos variables, digamos i y j , para los índices de la primera y segunda mitad respectivamente.
- Incremente j hasta arr[i] > K * arr[j] y j < tamaño de la segunda mitad. Agregue (j – (mid + 1)) a la respuesta e incremente i .
- Después de completar los pasos anteriores, imprima el valor de la respuesta como el número requerido de pares.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to merge two sorted arrays
int merge(int arr[], int temp[],
int l, int m, int r, int K)
{
// i: index to left subarray
int i = l;
// j: index to right subarray
int j = m + 1;
// Stores count of pairs that
// satisfy the given condition
int cnt = 0;
for (int i = l; i <= m; i++) {
bool found = false;
// Traverse to check for the
// valid conditions
while (j <= r) {
// If condition satisfies
if (arr[i] >= K * arr[j]) {
found = true;
j++;
}
else
break;
}
// While a[i] > K*a[j] satisfies
// increase j
// All elements in the right
// side of the left subarray
// also satisfies
if (found) {
cnt += j - (m + 1);
j--;
}
}
// Sort the two given arrays and
// store in the resultant array
int k = l;
i = l;
j = m + 1;
while (i <= m && j <= r) {
if (arr[i] <= arr[j])
temp[k++] = arr[i++];
else
temp[k++] = arr[j++];
}
// Elements which are left
// in the left subarray
while (i <= m)
temp[k++] = arr[i++];
// Elements which are left
// in the right subarray
while (j <= r)
temp[k++] = arr[j++];
for (int i = l; i <= r; i++)
arr[i] = temp[i];
// Return the count obtained
return cnt;
}
// Function to partition array into two halves
int mergeSortUtil(int arr[], int temp[],
int l, int r, int K)
{
int cnt = 0;
if (l < r) {
// Same as (l + r) / 2, but avoids
// overflow for large l and h
int m = (l + r) / 2;
// Sort first and second halves
cnt += mergeSortUtil(arr, temp,
l, m, K);
cnt += mergeSortUtil(arr, temp,
m + 1, r, K);
// Call the merging function
cnt += merge(arr, temp, l,
m, r, K);
}
return cnt;
}
// Function to print the count of
// required pairs using Merge Sort
void mergeSort(int arr[], int N, int K)
{
int temp[N];
cout << mergeSortUtil(arr, temp, 0,
N - 1, K);
}
// Driver code
int main()
{
int arr[] = { 5, 6, 2, 5 };
int N = sizeof(arr) / sizeof(arr[0]);
int K = 2;
// Function Call
mergeSort(arr, N, K);
return 0;
}
Java
// Java program for the above approach
class GFG
{
// Function to merge two sorted arrays
static int merge(int arr[], int temp[],
int l, int m, int r, int K)
{
// i: index to left subarray
int i = l;
// j: index to right subarray
int j = m + 1;
// Stores count of pairs that
// satisfy the given condition
int cnt = 0;
for (i = l; i <= m; i++)
{
boolean found = false;
// Traverse to check for the
// valid conditions
while (j <= r)
{
// If condition satisfies
if (arr[i] >= K * arr[j])
{
found = true;
}
else
break;
j++;
}
// While a[i] > K*a[j] satisfies
// increase j
// All elements in the right
// side of the left subarray
// also satisfies
if (found == true)
{
cnt += j - (m + 1);
j--;
}
}
// Sort the two given arrays and
// store in the resultant array
int k = l;
i = l;
j = m + 1;
while (i <= m && j <= r)
{
if (arr[i] <= arr[j])
temp[k++] = arr[i++];
else
temp[k++] = arr[j++];
}
// Elements which are left
// in the left subarray
while (i <= m)
temp[k++] = arr[i++];
// Elements which are left
// in the right subarray
while (j <= r)
temp[k++] = arr[j++];
for (i = l; i <= r; i++)
arr[i] = temp[i];
// Return the count obtained
return cnt;
}
// Function to partition array into two halves
static int mergeSortUtil(int arr[], int temp[],
int l, int r, int K)
{
int cnt = 0;
if (l < r)
{
// Same as (l + r) / 2, but avoids
// overflow for large l and h
int m = (l + r) / 2;
// Sort first and second halves
cnt += mergeSortUtil(arr, temp,
l, m, K);
cnt += mergeSortUtil(arr, temp,
m + 1, r, K);
// Call the merging function
cnt += merge(arr, temp, l,
m, r, K);
}
return cnt;
}
// Function to print the count of
// required pairs using Merge Sort
static void mergeSort(int arr[], int N, int K)
{
int temp[] = new int[N];
System.out.print(mergeSortUtil(arr, temp, 0, N - 1, K));
}
// Driver code
public static void main (String[] args)
{
int arr[] = { 5, 6, 2, 5 };
int N = arr.length;
int K = 2;
// Function Call
mergeSort(arr, N, K);
}
}
// This code is contributed by AnkThon
Python3
# Python3 program for the above approach # Function to merge two sorted arrays def merge(arr, temp, l, m, r, K) : # i: index to left subarray i = l # j: index to right subarray j = m + 1 # Stores count of pairs that # satisfy the given condition cnt = 0 for l in range(m + 1) : found = False # Traverse to check for the # valid conditions while (j <= r) : # If condition satisfies if (arr[i] >= K * arr[j]) : found = True else : break j += 1 # While a[i] > K*a[j] satisfies # increase j # All elements in the right # side of the left subarray # also satisfies if (found) : cnt += j - (m + 1) j -= 1 # Sort the two given arrays and # store in the resultant array k = l i = l j = m + 1 while (i <= m and j <= r) : if (arr[i] <= arr[j]) : temp[k] = arr[i] k += 1 i += 1 else : temp[k] = arr[j] k += 1 j += 1 # Elements which are left # in the left subarray while (i <= m) : temp[k] = arr[i] k += 1 i += 1 # Elements which are left # in the right subarray while (j <= r) : temp[k] = arr[j] k += 1 j += 1 for i in range(l, r + 1) : arr[i] = temp[i] # Return the count obtained return cnt # Function to partition array into two halves def mergeSortUtil(arr, temp, l, r, K) : cnt = 0 if (l < r) : # Same as (l + r) / 2, but avoids # overflow for large l and h m = (l + r) // 2 # Sort first and second halves cnt += mergeSortUtil(arr, temp, l, m, K) cnt += mergeSortUtil(arr, temp, m + 1, r, K) # Call the merging function cnt += merge(arr, temp, l, m, r, K) return cnt # Function to print the count of # required pairs using Merge Sort def mergeSort(arr, N, K) : temp = [0]*N print(mergeSortUtil(arr, temp, 0, N - 1, K)) # Driver code arr = [ 5, 6, 2, 5 ] N = len(arr) K = 2 # Function Call mergeSort(arr, N, K) # This code is contributed by divyeshrabadiya07.
C#
// C# program for the above approach
using System;
class GFG {
// Function to merge two sorted arrays
static int merge(int[] arr, int[] temp, int l, int m,
int r, int K)
{
// i: index to left subarray
int i = l;
// j: index to right subarray
int j = m + 1;
// Stores count of pairs that
// satisfy the given condition
int cnt = 0;
for (i = l; i <= m; i++) {
bool found = false;
// Traverse to check for the
// valid conditions
while (j <= r) {
// If condition satisfies
if (arr[i] >= K * arr[j]) {
found = true;
}
else
break;
j++;
}
// While a[i] > K*a[j] satisfies
// increase j
// All elements in the right
// side of the left subarray
// also satisfies
if (found == true) {
cnt += j - (m + 1);
j--;
}
}
// Sort the two given arrays and
// store in the resultant array
int k = l;
i = l;
j = m + 1;
while (i <= m && j <= r)
{
if (arr[i] <= arr[j])
temp[k++] = arr[i++];
else
temp[k++] = arr[j++];
}
// Elements which are left
// in the left subarray
while (i <= m)
temp[k++] = arr[i++];
// Elements which are left
// in the right subarray
while (j <= r)
temp[k++] = arr[j++];
for (i = l; i <= r; i++)
arr[i] = temp[i];
// Return the count obtained
return cnt;
}
// Function to partition array into two halves
static int mergeSortUtil(int[] arr, int[] temp, int l,
int r, int K)
{
int cnt = 0;
if (l < r) {
// Same as (l + r) / 2, but avoids
// overflow for large l and h
int m = (l + r) / 2;
// Sort first and second halves
cnt += mergeSortUtil(arr, temp, l, m, K);
cnt += mergeSortUtil(arr, temp, m + 1, r, K);
// Call the merging function
cnt += merge(arr, temp, l, m, r, K);
}
return cnt;
}
// Function to print the count of
// required pairs using Merge Sort
static void mergeSort(int[] arr, int N, int K)
{
int[] temp = new int[N];
Console.WriteLine(
mergeSortUtil(arr, temp, 0, N - 1, K));
}
// Driver code
static public void Main()
{
int[] arr = new int[] { 5, 6, 2, 5 };
int N = arr.Length;
int K = 2;
// Function Call
mergeSort(arr, N, K);
}
}
// This code is contributed by Dharanendra L V
Javascript
<script>
// Javascript program for the above approach
// Function to merge two sorted arrays
function merge(arr, temp, l, m, r, K)
{
// i: index to left subarray
let i = l;
// j: index to right subarray
let j = m + 1;
// Stores count of pairs that
// satisfy the given condition
let cnt = 0;
for(i = l; i <= m; i++)
{
let found = false;
// Traverse to check for the
// valid conditions
while (j <= r)
{
// If condition satisfies
if (arr[i] >= K * arr[j])
{
found = true;
}
else
break;
j++;
}
// While a[i] > K*a[j] satisfies
// increase j
// All elements in the right
// side of the left subarray
// also satisfies
if (found == true)
{
cnt += j - (m + 1);
j--;
}
}
// Sort the two given arrays and
// store in the resultant array
let k = l;
i = l;
j = m + 1;
while (i <= m && j <= r)
{
if (arr[i] <= arr[j])
temp[k++] = arr[i++];
else
temp[k++] = arr[j++];
}
// Elements which are left
// in the left subarray
while (i <= m)
temp[k++] = arr[i++];
// Elements which are left
// in the right subarray
while (j <= r)
temp[k++] = arr[j++];
for(i = l; i <= r; i++)
arr[i] = temp[i];
// Return the count obtained
return cnt;
}
// Function to partition array into two halves
function mergeSortUtil(arr, temp, l, r, K)
{
let cnt = 0;
if (l < r)
{
// Same as (l + r) / 2, but avoids
// overflow for large l and h
let m = parseInt((l + r) / 2, 10);
// Sort first and second halves
cnt += mergeSortUtil(arr, temp,
l, m, K);
cnt += mergeSortUtil(arr, temp,
m + 1, r, K);
// Call the merging function
cnt += merge(arr, temp, l, m, r, K);
}
return cnt;
}
// Function to print the count of
// required pairs using Merge Sort
function mergeSort(arr, N, K)
{
let temp = new Array(N);
document.write(mergeSortUtil(
arr, temp, 0, N - 1, K));
}
// Driver code
let arr = [ 5, 6, 2, 5 ];
let N = arr.length;
let K = 2;
// Function Call
mergeSort(arr, N, K);
// This code is contributed by divyesh072019
</script>
Producción
2
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)