Dada una array , arr[] de N elementos y un entero K , la tarea es encontrar el número de pares (i, j) tales que el valor absoluto de (arr[i] – arr[j]) sea un múltiplo de k _
Ejemplos:
Entrada: N = 4, K = 2, arr[] = {1, 2, 3, 4}
Salida: 2
Explicación: Hay un total de 2 pares en la array con una diferencia absoluta divisible por 2. Los pares son: (1, 3 ), (2, 4).Entrada: N = 3, K = 3, arr[] = {3, 3, 3}
Salida: 3
Explicación: Hay un total de 3 pares en esta array con una diferencia absoluta divisible por 3. Los pares son: (3, 3), (3, 3), (3, 3).
Enfoque ingenuo: la forma más fácil es iterar a través de cada par posible en la array y si la diferencia absoluta de los números es un múltiplo de K , entonces aumente el conteo en 1 . Imprime el valor del conteo después de procesar todos los pares.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque de array de frecuencias: el enfoque para resolver este problema utilizando una array de frecuencias se analiza en el Conjunto 1 de este artículo . En este enfoque, hemos discutido el enfoque para resolverlo usando el mapa.
Enfoque eficiente: Para optimizar el enfoque anterior, la idea es observar el hecho de que para dos números a[i] y a[j] , si a[i] % k = a[j] % k , entonces abs(a[ i] – a[j]) es un múltiplo de K . Siga los pasos a continuación para resolver el problema:
- Inicialice la variable ans como 0 para almacenar la respuesta.
- Declare un mapa_desordenado<int, int> count_map[] que almacena el recuento de restos de elementos de array con K .
- Itere sobre el rango [1, N] usando el índice variable e incremente el valor arr[index]%k en el mapa de conteo en 1 para cada índice.
- Iterar sobre todos los pares clave-valor en count_map . Para cada par clave-valor:
- El valor count_map[rem] es el número de elementos cuyo resto con K es igual a ‘ rem ‘.
- Para que se forme un par válido, seleccione dos números cualesquiera de los números count_map[rem] .
- El número de formas de seleccionar dos números de ‘ N ‘ números es Nc2 = N * (N – 1) / 2 .
- Agregue la respuesta de todos los pares clave-valor e imprima ans .
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 number of pairs
// (i, j) such that abs(arr[i] - arr[j])
// is divisible by k.
void countOfPairs(int* arr, int N, int K)
{
// Frequency Map to keep count of
// remainders of array elements with K.
unordered_map<int, int> count_map;
for (int index = 0; index < N; ++index) {
count_map[arr[index] % K]++;
}
// To store the final answer.
int ans = 0;
for (auto it : count_map) {
// Number of ways of selecting any two
// numbers from all numbers having the
// same remainder is Nc2 = N
// * (N - 1) / 2
ans += (it.second * (it.second - 1)) / 2;
}
// Output the answer.
cout << ans << endl;
}
// Driver Code
int main()
{
int K = 2;
// Input array
int arr[] = { 1, 2, 3, 4 };
// Size of array
int N = sizeof arr / sizeof arr[0];
countOfPairs(arr, N, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to count number of pairs
// (i, j) such that Math.abs(arr[i] - arr[j])
// is divisible by k.
static void countOfPairs(int[] arr, int N, int K) {
// Frequency Map to keep count of
// remainders of array elements with K.
HashMap<Integer, Integer> count_map =
new HashMap<Integer, Integer>();
for (int index = 0; index < N; ++index) {
if (count_map.containsKey(arr[index] % K)) {
count_map.put(arr[index] % K,
count_map.get(arr[index] % K) + 1);
} else {
count_map.put(arr[index] % K, 1);
}
}
// To store the final answer.
int ans = 0;
for (Map.Entry<Integer, Integer> it : count_map.entrySet()) {
// Number of ways of selecting any two
// numbers from all numbers having the
// same remainder is Nc2 = N
// * (N - 1) / 2
ans += (it.getValue() * (it.getValue() - 1)) / 2;
}
// Output the answer.
System.out.print(ans + "\n");
}
// Driver Code
public static void main(String[] args) {
int K = 2;
// Input array
int arr[] = { 1, 2, 3, 4 };
// Size of array
int N = arr.length;
countOfPairs(arr, N, K);
}
}
// This code is contributed by shikhasingrajput
Python3
# Python Program to implement
# the above approach
# Function to count number of pairs
# (i, j) such that abs(arr[i] - arr[j])
# is divisible by k.
def countOfPairs(arr, N, K):
# Frequency Map to keep count of
# remainders of array elements with K.
count_map = {}
for index in range(N):
if (not arr[index] % K in count_map):
count_map[arr[index] % K] = 1
else:
count_map[arr[index] % K] += 1
# To store the final answer.
ans = 0
for val in count_map.values():
# Number of ways of selecting any two
# numbers from all numbers having the
# same remainder is Nc2 = N
# * (N - 1) / 2
ans += (val * (val - 1)) // 2
# Output the answer.
print(ans)
# Driver Code
K = 2
# Input array
arr = [1, 2, 3, 4]
# Size of array
N = len(arr)
countOfPairs(arr, N, K)
# This code is contributed by Saurabh Jaiswal
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG {
// Function to count number of pairs
// (i, j) such that Math.Abs(arr[i] - arr[j])
// is divisible by k.
static void countOfPairs(int[] arr, int N, int K) {
// Frequency Map to keep count of
// remainders of array elements with K.
Dictionary<int, int> count_map =
new Dictionary<int, int>();
for (int index = 0; index < N; ++index) {
if (count_map.ContainsKey(arr[index] % K)) {
count_map[arr[index] % K] =
count_map[arr[index] % K] + 1;
} else {
count_map.Add(arr[index] % K, 1);
}
}
// To store the readonly answer.
int ans = 0;
foreach (KeyValuePair<int, int> it in count_map) {
// Number of ways of selecting any two
// numbers from all numbers having the
// same remainder is Nc2 = N
// * (N - 1) / 2
ans += (it.Value * (it.Value - 1)) / 2;
}
// Output the answer.
Console.Write(ans + "\n");
}
// Driver Code
public static void Main(String[] args) {
int K = 2;
// Input array
int []arr = { 1, 2, 3, 4 };
// Size of array
int N = arr.Length;
countOfPairs(arr, N, K);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to count number of pairs
// (i, j) such that abs(arr[i] - arr[j])
// is divisible by k.
function countOfPairs(arr, N, K) {
// Frequency Map to keep count of
// remainders of array elements with K.
let count_map = new Map();
for (let index = 0; index < N; ++index) {
if (!count_map.has(arr[index] % K))
count_map.set(arr[index] % K, 1);
else
count_map.set(arr[index] % K, count_map.get(arr[index] % K) + 1)
}
// To store the final answer.
let ans = 0;
for (let [key, value] of count_map) {
// Number of ways of selecting any two
// numbers from all numbers having the
// same remainder is Nc2 = N
// * (N - 1) / 2
ans += (value * (value - 1)) / 2;
}
// Output the answer.
document.write(ans + '<br>');
}
// Driver Code
let K = 2;
// Input array
let arr = [1, 2, 3, 4];
// Size of array
let N = arr.length;
countOfPairs(arr, N, K);
// This code is contributed by Potta Lokesh
</script>
2
Complejidad temporal: O(NlogN)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por shreyasshetty788 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA