Dada una array arr[] de tamaño N y tres enteros X , Y y K , la tarea es contar el número de pares (i, j) donde i < j tal que (arr[i] * X + arr[j] * Y) = K.
Ejemplos :
Entrada : arr[] = {3, 1, 2, 3}, X = 4, Y = 2, K = 14
Salida : 2
Explicación : Los pares posibles son: (1, 2), (3, 4).
Para i = 1, j = 2 , Valor de la expresión = 4 * 3 + 2 * 1 = 14 .
Para i = 3, j = 4 , Valor de la expresión = 4 * 2 + 2 * 3 = 14 .Entrada : arr[] = [1, 3, 2], X = 1, Y = 3, K = 7
Salida : 1
Explicación : Los pares posibles son: (1, 2).
Para i = 1, j = 2 , Valor de la expresión = 1 * 1 + 2 * 3 = 7 .Entrada : N = 2, arr[] = [1, 2], X = 1, Y = 1, objetivo = 2
Salida : 0
Explicación : ningún par cumple la condición anterior.
Para i = 1, j = 2, Valor de la expresión = 1 * 1 + 1 * 2 = 3.
Enfoque ingenuo: la idea básica para resolver el problema es la siguiente:
Encuentre todos los pares posibles de (i, j) y para cada par verifique si (arr[i]*X + arr[j]*Y = K). Si es así, incremente el conteo de pares.
Siga los siguientes pasos para implementar la idea:
- Inicialice, una variable entera (digamos cnt como 0 ) para almacenar el recuento de los pares.
- Recorra la array desde i = 0 hasta N – 2 :
- Bucle para todos los segundos elementos de j = i + 1 a N-1 :
- Comprueba si la suma de arr[i] * X y arr[j] * Y es igual a K.
- Luego incrementa el valor de cnt en 1.
- Bucle para todos los segundos elementos de j = i + 1 a N-1 :
- Devuelve el valor de cnt como respuesta final.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function to count the number of pairs
int countPairs(int arr[], int n, int x,
int y, int k)
{
// Store the count of the pairs.
int cnt = 0;
// Loop for the first element.
for (int i = 0; i < n - 1; ++i) {
// Loop for the second element.
for (int j = i + 1; j < n; ++j) {
// Calculate the sum
int cur_sum = arr[i] * x
+ arr[j] * y;
// Increment 'cnt' if current
// sum is equal to required target
if (cur_sum == k) {
cnt++;
}
}
}
// Return the count of pairs.
return cnt;
}
// Driver Code
int main()
{
int X = 4, Y = 2, K = 14;
int arr[] = { 3, 1, 2, 3 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
cout << countPairs(arr, N, X, Y, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
public class GFG
{
// Function to count the number of pairs
static int countPairs(int[] arr, int n, int x,
int y, int k)
{
// Store the count of the pairs.
int cnt = 0;
// Loop for the first element.
for (int i = 0; i < n - 1; ++i) {
// Loop for the second element.
for (int j = i + 1; j < n; ++j) {
// Calculate the sum
int cur_sum = arr[i] * x
+ arr[j] * y;
// Increment 'cnt' if current
// sum is equal to required target
if (cur_sum == k) {
cnt++;
}
}
}
// Return the count of pairs.
return cnt;
}
// Driver Code
public static void main(String[] args)
{
int X = 4, Y = 2, K = 14;
int[] arr = { 3, 1, 2, 3 };
int N = arr.length;
// Function call
System.out.println( countPairs(arr, N, X, Y, K));
}
}
// This code is contributed by shinjanpatra.
Python3
# Python code for the above approach # Function to count the number of pairs def countPairs(arr, n, x, y, k) : # Store the count of the pairs. cnt = 0 # Loop for the first element. for i in range(n-1) : # Loop for the second element. for j in range(i+1, n) : # Calculate the sum cur_sum = arr[i] * x + arr[j] * y # Increment 'cnt' if current # sum is equal to required target if (cur_sum == k) : cnt += 1 # Return the count of pairs. return cnt # Driver Code if __name__ == "__main__": X = 4 Y = 2 K = 14 arr = [ 3, 1, 2, 3 ] N = len(arr) # Function call print(countPairs(arr, N, X, Y, K)) # This code is contributed by code_hunt.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to count the number of pairs
static int countPairs(int[] arr, int n, int x,
int y, int k)
{
// Store the count of the pairs.
int cnt = 0;
// Loop for the first element.
for (int i = 0; i < n - 1; ++i) {
// Loop for the second element.
for (int j = i + 1; j < n; ++j) {
// Calculate the sum
int cur_sum = arr[i] * x
+ arr[j] * y;
// Increment 'cnt' if current
// sum is equal to required target
if (cur_sum == k) {
cnt++;
}
}
}
// Return the count of pairs.
return cnt;
}
// Driver Code
public static void Main(String[] args)
{
int X = 4, Y = 2, K = 14;
int[] arr = { 3, 1, 2, 3 };
int N = arr.Length;
// Function call
Console.WriteLine( countPairs(arr, N, X, Y, K));
}
}
// This code is contributed by avijitmondal1998.
Javascript
<script>
// JavaScript code to implement the approach
// Function to count the number of pairs
function countPairs(arr, n, x, y, k)
{
// Store the count of the pairs.
var cnt = 0;
// Loop for the first element.
for (var i = 0; i < n - 1; ++i) {
// Loop for the second element.
for (var j = i + 1; j < n; ++j) {
// Calculate the sum
var cur_sum = arr[i] * x + arr[j] * y;
// Increment 'cnt' if current
// sum is equal to required target
if (cur_sum == k) {
cnt++;
}
}
}
// Return the count of pairs.
return cnt;
}
// Driver Code
var X = 4;
var Y = 2;
var K = 14;
var arr = [ 3, 1, 2, 3 ];
var N = arr.length;
// Function call
document.write(countPairs(arr, N, X, Y, K));
// this code is contributed by phasing17.
</script>
Producción
2
Complejidad de tiempo : O(N 2 )
Complejidad de espacio : O(1)
Enfoque eficiente: el problema se puede resolver de manera eficiente con base en la siguiente observación matemática:
arr[i]*X + arr[j]*Y = K
arr[i]*X = K – arr[j]*Y
Entonces (K – arr[j]*Y) debe ser divisible por X y si arr[ j], entonces el valor de arr[i] debe ser (K – arr[j]*Y)/X .Entonces, para resolver el problema basado en la observación anterior, considere cada valor como arr[j] e intente encontrar la presencia de arr[i] usando la relación anterior donde i es menor que j .
La observación anterior se puede implementar utilizando el conteo de frecuencia . Siga los pasos a continuación para resolver este problema:
- Inicialice una variable (por ejemplo, cnt = 0 ) para almacenar el recuento de pares.
- Cree una array de frecuencia freq[] para almacenar la frecuencia de los elementos de la array.
- Recorra todos los elementos desde j = 0 hasta N-1 :
- Encuentre el valor de arr[i] requerido como se muestra en la observación anterior.
- Si ese elemento está presente, aumente el cnt por la frecuencia de ese elemento.
- Aumente la frecuencia de arr[j] .
- Devuelve el valor de cnt como respuesta final.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the count of pairs
int countPairs(int arr[], int n, int x,
int y, int k)
{
// Variable to store count of the pairs
int cnt = 0;
// Map for storing the frequency
unordered_map<int, int> freq;
// Loop for finding the count of pairs
for (int i = 0; i < n; ++i) {
// RHS Value of the equation given
// in approach.
int rhs = k - arr[i] * y;
// If RHS value is not divisible by
// x or is negative, there is no pair
// possible for 'arr[i]' as second
// element.
if (rhs % x || rhs <= 0) {
// Update the frequency of arr[i]
freq[arr[i]]++;
continue;
}
rhs /= x;
// Adding frequency of rhs in array
cnt += freq[rhs];
// Update the frequency of arr[i]
freq[arr[i]]++;
}
// Return the count of pairs
return cnt;
}
// Driver Code
int main()
{
int X = 4, Y = 2, K = 14;
int arr[] = { 3, 1, 2, 3 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
cout << countPairs(arr, N, X, Y, K);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
public class GFG
{
// Function to find the count of pairs
static int countPairs(int[] arr, int n, int x,
int y, int k)
{
// Variable to store count of the pairs
int cnt = 0;
// Map for storing the frequency
Map<Integer,Integer> freq = new HashMap<Integer,Integer>();
for (int i = 0; i < n; i++) {
if(freq.containsKey(arr[i])){
freq.put(arr[i], freq.get(arr[i]) + 0);
}else{
freq.put(arr[i], 0);
}
}
// Loop for finding the count of pairs
for (int i = 0; i < n; ++i) {
// RHS Value of the equation given
// in approach.
int rhs = k - arr[i] * y;
// If RHS value is not divisible by
// x or is negative, there is no pair
// possible for 'arr[i]' as second
// element.
if ((rhs % x) != 0 || rhs <= 0) {
// Update the frequency of arr[i]
freq.put(arr[i], freq.get(arr[i])+ 1);
continue;
}
rhs /= x;
// Adding frequency of rhs in array
cnt += freq.get(rhs);
// Update the frequency of arr[i]
freq.put(arr[i], freq.get(arr[i])+ 1);
}
// Return the count of pairs
return cnt;
}
// Driver Code
public static void main(String []args)
{
int X = 4, Y = 2, K = 14;
int[] arr = { 3, 1, 2, 3 };
int N = arr.length;
// Function call
System.out.print(countPairs(arr, N, X, Y, K));
}
}
// This code is contributed by AnkThon
Python3
# Python3 program for the above approach # Function to find the count of pairs def countPairs(arr, n, x, y, k): # Variable to store count of the pairs cnt = 0 # Dictionary for storing the frequency freq = dict() # Loop for finding the count of pairs for i in range(n): # RHS Value of the equation given # in approach. rhs = k - arr[i] * y; # If RHS value is not divisible by # x or is negative, there is no pair # possible for 'arr[i]' as second # element. if (rhs % x or rhs <= 0) : # Update the frequency of arr[i] if arr[i] in freq: freq[arr[i]] += 1 else: freq[arr[i]] = 1 continue rhs = rhs // x # Adding frequency of rhs in array if rhs in freq: cnt += freq[rhs] # Update the frequency of arr[i] if arr[i] in freq: freq[arr[i]] += 1 else: freq[arr[i]] = 1 # Return the count of pairs return cnt; # Driver Code X = 4 Y = 2 K = 14; arr = [3, 1, 2, 3] N = len(arr) # Function Call print(countPairs(arr, N, X, Y, K)) # This code is contributed by phasing17
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to find the count of pairs
static int countPairs(int[] arr, int n, int x,
int y, int k)
{
// Variable to store count of the pairs
int cnt = 0;
// Map for storing the frequency
Dictionary<int,int> freq = new Dictionary<int,int>();
for (int i = 0; i < n; i++) {
if(freq.ContainsKey(arr[i])){
freq[arr[i]] = freq[arr[i]] + 0;
}else{
freq.Add(arr[i], 0);
}
}
// Loop for finding the count of pairs
for (int i = 0; i < n; ++i) {
// RHS Value of the equation given
// in approach.
int rhs = k - arr[i] * y;
// If RHS value is not divisible by
// x or is negative, there is no pair
// possible for 'arr[i]' as second
// element.
if ((rhs % x) != 0 || rhs <= 0) {
// Update the frequency of arr[i]
// Update the frequency of arr[i]
freq[arr[i]]++;
continue;
}
rhs /= x;
// Adding frequency of rhs in array
cnt += freq[rhs];
// Update the frequency of arr[i]
freq[arr[i]]++;
}
// Return the count of pairs
return cnt;
}
// Driver Code
public static void Main()
{
int X = 4, Y = 2, K = 14;
int[] arr = { 3, 1, 2, 3 };
int N = arr.Length;
// Function call
Console.Write(countPairs(arr, N, X, Y, K));
}
}
Javascript
<script>
// JavaScript program for the above approach
// Function to find the count of pairs
function countPairs(arr, n, x, y, k)
{
// Variable to store count of the pairs
let cnt = 0;
// Map for storing the frequency
let freq = new Map();
// Loop for finding the count of pairs
for (let i = 0; i < n; ++i) {
// RHS Value of the equation given
// in approach.
let rhs = k - arr[i] * y;
// If RHS value is not divisible by
// x or is negative, there is no pair
// possible for 'arr[i]' as second
// element.
if (rhs % x || rhs <= 0) {
// Update the frequency of arr[i]
if (freq.has(arr[i])) {
freq.set(arr[i], freq.get(arr[i]) + 1)
}
else {
freq.set(arr[i], 1)
}
continue;
}
rhs = Math.floor(rhs / x);
// Adding frequency of rhs in array
if (freq.has(arr[i]))
cnt += freq.get(arr[i]) + 1;
// Update the frequency of arr[i]
if (freq.has(arr[i]))
freq.set(arr[i], freq.get(arr[i]) + 1)
else
freq.set(arr[i], 1)
}
// Return the count of pairs
return cnt;
}
// Driver Code
let X = 4, Y = 2, K = 14;
let arr = [3, 1, 2, 3];
let N = arr.length;
// Function call
document.write(countPairs(arr, N, X, Y, K));
// This code is contributed by Potta Lokesh
</script>
Producción
2
Tiempo Complejidad : O(N)
Espacio Auxiliar : O(N)