Dadas cuatro arrays que contienen elementos enteros y una suma de enteros , la tarea es contar los cuatrillizos de modo que cada elemento se elija de una array diferente y la suma de los cuatro elementos sea igual a la suma dada.
Ejemplos:
Entrada: P[] = {0, 2}, Q[] = {-1, -2}, R[] = {2, 1}, S[] = {2, -1}, sum = 0
Salida: 2
(0, -1, 2, -1) y (2, -2, 1, -1) son los cuatrillizos requeridos.
Entrada: P[] = {1, -1, 2, 3, 4}, Q[] = {3, 2, 4}, R[] = {-2, -1, 2, 1}, S[] = {4, -1}, suma = 3
Salida: 10
Enfoque: Genere todos los cuatrillizos posibles y calcule la suma de cada cuatrillizos. Cuente todos los cuatrillizos cuya suma sea igual a la suma dada.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the count of the required quadruplets
int countQuadruplets(int arr1[], int n1, int arr2[], int n2,
int arr3[], int n3, int arr4[], int n4, int sum)
{
// To store the count of required quadruplets
int cnt = 0;
// For arr1[]
for (int i = 0; i < n1; i++) {
// For arr2[]
for (int j = 0; j < n2; j++) {
// For arr3[]
for (int k = 0; k < n3; k++) {
// For arr4[]
for (int l = 0; l < n4; l++) {
// If current quadruplet has the required sum
if (arr1[i] + arr2[j] + arr3[k] + arr4[l] == sum) {
cnt++;
}
}
}
}
}
return cnt;
}
// Driver code
int main()
{
int arr1[] = { 0, 2 };
int arr2[] = { -1, -2 };
int arr3[] = { 2, 1 };
int arr4[] = { 2, -1 };
int sum = 0;
int n1 = sizeof(arr1) / sizeof(arr1[0]);
int n2 = sizeof(arr2) / sizeof(arr2[0]);
int n3 = sizeof(arr3) / sizeof(arr3[0]);
int n4 = sizeof(arr4) / sizeof(arr4[0]);
cout << countQuadruplets(arr1, n1, arr2, n2, arr3, n3, arr4, n4, sum);
return 0;
}
Java
// Java program to implement
// the above approach
class GFG
{
// Function to return the count of the required quadruplets
static int countQuadruplets(int arr1[], int n1, int arr2[], int n2,
int arr3[], int n3, int arr4[], int n4, int sum)
{
// To store the count of required quadruplets
int cnt = 0;
// For arr1[]
for (int i = 0; i < n1; i++)
{
// For arr2[]
for (int j = 0; j < n2; j++)
{
// For arr3[]
for (int k = 0; k < n3; k++)
{
// For arr4[]
for (int l = 0; l < n4; l++)
{
// If current quadruplet has the required sum
if (arr1[i] + arr2[j] + arr3[k] + arr4[l] == sum)
{
cnt++;
}
}
}
}
}
return cnt;
}
// Driver code
public static void main(String[] args)
{
int arr1[] = { 0, 2 };
int arr2[] = { -1, -2 };
int arr3[] = { 2, 1 };
int arr4[] = { 2, -1 };
int sum = 0;
int n1 = arr1.length;
int n2 = arr2.length;
int n3 = arr3.length;
int n4 = arr4.length;
System.out.println(countQuadruplets(arr1, n1, arr2, n2,
arr3, n3, arr4, n4, sum));
}
}
// This code contributed by Rajput-Ji
Python3
# Python implementation of the approach # Function to return the count of the required quadruplets def countQuadruplets(P, Q, R, S, sum): # To store the count of required quadruplets cnt = 0 # Using four loops generate all possible quadruplets for elem1 in P: for elem2 in Q: for elem3 in R: for elem4 in S: if elem1 + elem2 + elem3 + elem4 == sum: cnt = cnt + 1 return cnt # Driver code P = [ 0, 2] Q = [-1, -2] R = [2, 1] S = [ 2, -1] sum = 0 print(countQuadruplets(P, Q, R, S, sum))
C#
// C# program to implement
// the above approach
using System;
class GFG
{
// Function to return the count of the required quadruplets
static int countQuadruplets(int []arr1, int n1, int []arr2, int n2,
int []arr3, int n3, int []arr4, int n4, int sum)
{
// To store the count of required quadruplets
int cnt = 0;
// For arr1[]
for (int i = 0; i < n1; i++)
{
// For arr2[]
for (int j = 0; j < n2; j++)
{
// For arr3[]
for (int k = 0; k < n3; k++)
{
// For arr4[]
for (int l = 0; l < n4; l++)
{
// If current quadruplet has the required sum
if (arr1[i] + arr2[j] + arr3[k] + arr4[l] == sum)
{
cnt++;
}
}
}
}
}
return cnt;
}
// Driver code
static public void Main ()
{
int []arr1 = { 0, 2 };
int []arr2 = { -1, -2 };
int []arr3 = { 2, 1 };
int []arr4 = { 2, -1 };
int sum = 0;
int n1 = arr1.Length;
int n2 = arr2.Length;
int n3 = arr3.Length;
int n4 = arr4.Length;
Console.WriteLine(countQuadruplets(arr1, n1, arr2, n2,
arr3, n3, arr4, n4, sum));
}
}
// This code contributed by akt_mit
PHP
<?php
// PHP implementation of the approach
// Function to return the count of the required quadruplets
function countQuadruplets($arr1, $n1, $arr2,$n2,
$arr3, $n3, $arr4, $n4, $sum)
{
// To store the count of required quadruplets
$cnt = 0;
// For arr1[]
for ($i = 0; $i < $n1; $i++)
{
// For arr2[]
for ($j = 0; $j < $n2; $j++)
{
// For arr3[]
for ($k = 0; $k < $n3; $k++)
{
// For arr4[]
for ( $l = 0; $l < $n4; $l++)
{
// If current quadruplet has the required sum
if ($arr1[$i] + $arr2[$j] + $arr3[$k] +
$arr4[$l] == $sum)
{
$cnt++;
}
}
}
}
}
return $cnt;
}
// Driver code
$arr1 = array (0, 2 );
$arr2 = array( -1, -2 );
$arr3 = array( 2, 1 );
$arr4 =array( 2, -1 );
$sum = 0;
$n1 = count($arr1);
$n2 =count($arr2);
$n3 = count($arr3);
$n4 = count($arr4);
echo countQuadruplets($arr1, $n1, $arr2, $n2,
$arr3, $n3, $arr4, $n4, $sum);
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript program to implement the above approach
// Function to return the count of the required quadruplets
function countQuadruplets(arr1, n1, arr2, n2, arr3, n3, arr4, n4, sum)
{
// To store the count of required quadruplets
let cnt = 0;
// For arr1[]
for (let i = 0; i < n1; i++)
{
// For arr2[]
for (let j = 0; j < n2; j++)
{
// For arr3[]
for (let k = 0; k < n3; k++)
{
// For arr4[]
for (let l = 0; l < n4; l++)
{
// If current quadruplet has the required sum
if (arr1[i] + arr2[j] + arr3[k] + arr4[l] == sum)
{
cnt++;
}
}
}
}
}
return cnt;
}
let arr1 = [ 0, 2 ];
let arr2 = [ -1, -2 ];
let arr3 = [ 2, 1 ];
let arr4 = [ 2, -1 ];
let sum = 0;
let n1 = arr1.length;
let n2 = arr2.length;
let n3 = arr3.length;
let n4 = arr4.length;
document.write(countQuadruplets(arr1, n1, arr2, n2,
arr3, n3, arr4, n4, sum));
</script>
Producción:
2
Complejidad Temporal: O(n 4 )
Complejidad Espacial: O(1)
Enfoque eficiente: almacene la frecuencia de todas las sumas posibles de dos elementos de dos arrays diferentes en un mapa. Iterar sobre otras dos arrays y encontrar la suma de dos elementos en estas dos arrays, sea cur_sum . Si sum – cur_sum está presente en el mapa, esto significa que existen cuatro elementos en cuatro arrays diferentes cuya suma es igual a suma.
Implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the count of the required quadruplets
int countQuadruplets(int arr1[], int n1, int arr2[], int n2,
int arr3[], int n3, int arr4[], int n4, int sum)
{
// To store the count of required quadruplets
int cnt = 0;
// To store the frequency of sum of
// two elements of two different arrays
unordered_map<int,int> freq;
// For arr1[]
for (int i = 0; i < n1; i++) {
// For arr2[]
for (int j = 0; j < n2; j++) {
freq[arr1[i]+arr2[j]]++;
}
}
// for arr3[]
for (int i = 0; i < n3; i++) {
// For arr4[]
for (int j = 0; j < n4; j++) {
int cur_sum = arr3[i]+arr4[j];
cnt+=freq[sum-cur_sum];
}
}
return cnt;
}
// Driver code
int main()
{
int arr1[] = { 0, 2 };
int arr2[] = { -1, -2 };
int arr3[] = { 2, 1 };
int arr4[] = { 2, -1 };
int sum = 0;
int n1 = sizeof(arr1) / sizeof(arr1[0]);
int n2 = sizeof(arr2) / sizeof(arr2[0]);
int n3 = sizeof(arr3) / sizeof(arr3[0]);
int n4 = sizeof(arr4) / sizeof(arr4[0]);
cout << countQuadruplets(arr1, n1, arr2, n2, arr3, n3, arr4, n4, sum);
return 0;
}
Python3
# Python3 implementation of the approach # Function to return the count of the required quadruplets from collections import defaultdict def countQuadruplets(arr1, n1, arr2, n2, arr, n3, arr4, n4, S): # To store the count of required quadruplets cnt = 0 # To store the frequency of S of # two elements of two different arrays freq = defaultdict(int) # For arr1[] for i in range(n1): # For arr2[] for j in range(n2): freq[arr1[i] + arr2[j]] += 1 # for arr3[] for i in range(n3): # For arr4[] for j in range(n4): cur_S = arr3[i] + arr4[j] cnt += freq[S - cur_S] return cnt # Driver code if __name__ == "__main__": arr1 = [0, 2] arr2 = [-1, -2] arr3 = [2, 1] arr4 = [2, -1] S = 0 n1 = len(arr1) n2 = len(arr2) n3 = len(arr3) n4 = len(arr4) print(countQuadruplets(arr1, n1, arr2, n2, arr3, n3, arr4, n4, S))
Javascript
<script>
// JavaScript implementation of the approach
// Function to return the count of the required quadruplets
function countQuadruplets(arr1, n1, arr2, n2,
arr3, n3, arr4, n4, sum)
{
// To store the count of required quadruplets
let cnt = 0;
// To store the frequency of sum of
// two elements of two different arrays
let freq = new Map();
// For arr1
for (let i = 0; i < n1; i++) {
// For arr2
for (let j = 0; j < n2; j++) {
if(freq.has(arr1[i]+arr2[j])){
freq.set(arr1[i]+arr2[j],freq.get(arr1[i]+arr2[j])+1);
}
else
freq.set(arr1[i]+arr2[j],1);
}
}
// for arr3[]
for (let i = 0; i < n3; i++) {
// For arr4[]
for (let j = 0; j < n4; j++) {
let cur_sum = arr3[i]+arr4[j];
cnt+= freq.has(sum-cur_sum) == false? 0 : freq.get(sum-cur_sum);
}
}
return cnt;
}
// Driver code
let arr1 = [ 0, 2 ];
let arr2 = [ -1, -2 ];
let arr3 = [ 2, 1 ];
let arr4 = [ 2, -1 ];
let sum = 0;
let n1 = arr1.length;
let n2 = arr2.length;
let n3 = arr3.length;
let n4 = arr4.length;
document.write(countQuadruplets(arr1, n1, arr2, n2, arr3, n3, arr4, n4, sum));
// This code is contributed by shinjanpatra
</script>
Complejidad temporal: O(n*n)
Espacio Auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por everythingispossible y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA