Dada una array arr[] de tamaño N y un número entero S , la tarea es encontrar el recuento de cuatrillizos presentes en la array dada que tiene una suma S.
Ejemplos:
Entrada: arr[] = {1, 5, 3, 1, 2, 10}, S = 20
Salida: 1
Explicación: Solo el cuádruple que cumple las condiciones es arr[1] + arr[2] + arr[4] + arr [5] = 5 + 3 + 2 + 10 = 20.Entrada: N = 6, S = 13, arr[] = {4, 5, 3, 1, 2, 4}
Salida: 3
Explicación: Tres cuatrillizos con suma 13 son:
- array[0] + array[2] + array[4] + array[5] = 4 + 3 + 2 + 4 = 13
- array[0] + array[1] + array[2] + array[3] = 4 + 5 + 3 + 1 = 13
- array[1] + array[2] + array[3] + array[5] = 5 + 3 + 1 + 4 = 13
Enfoque ingenuo: la idea es generar todas las combinaciones posibles de longitud 4 a partir de la array dada. Para cada cuatrillizos, si la suma es igual a S , incremente el contador en 1 . Después de verificar todos los cuatrillizos, imprima el contador como el número total de cuatrillizos que tienen la suma S .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <iostream>
using namespace std;
// Function to return the number of
// quadruplets with the given sum
int countSum(int a[], int n, int sum)
{
// Initialize variables
int i, j, k, l;
// Initialize answer
int count = 0;
// All possible first elements
for (i = 0; i < n - 3; i++) {
// All possible second elements
for (j = i + 1; j < n - 2; j++) {
// All possible third elements
for (k = j + 1; k < n - 1; k++) {
// All possible fourth elements
for (l = k + 1; l < n; l++) {
// Increment counter by 1
// if quadruplet sum is S
if (a[i] + a[j]
+ a[k] + a[l]
== sum)
count++;
}
}
}
}
// Return the final count
return count;
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 4, 5, 3, 1, 2, 4 };
// Given sum S
int S = 13;
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
cout << countSum(arr, N, S);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to return the number of
// quadruplets with the given sum
static int countSum(int a[], int n, int sum)
{
// Initialize variables
int i, j, k, l;
// Initialize answer
int count = 0;
// All possible first elements
for(i = 0; i < n - 3; i++)
{
// All possible second elements
for(j = i + 1; j < n - 2; j++)
{
// All possible third elements
for(k = j + 1; k < n - 1; k++)
{
// All possible fourth elements
for(l = k + 1; l < n; l++)
{
// Increment counter by 1
// if quadruplet sum is S
if (a[i] + a[j] +
a[k] + a[l] == sum)
count++;
}
}
}
}
// Return the final count
return count;
}
// Driver Code
public static void main(String args[])
{
// Given array arr[]
int arr[] = { 4, 5, 3, 1, 2, 4 };
// Given sum S
int S = 13;
int N = arr.length;
// Function Call
System.out.print(countSum(arr, N, S));
}
}
// This code is contributed by bgangwar59
Python3
# Python3 program for the above approach # Function to return the number of # quadruplets with the given sum def countSum(a, n, sum): # Initialize variables # i, j, k, l # Initialize answer count = 0 # All possible first elements for i in range(n - 3): # All possible second elements for j in range(i + 1, n - 2): # All possible third elements for k in range(j + 1, n - 1): # All possible fourth elements for l in range(k + 1, n): # Increment counter by 1 # if quadruplet sum is S if (a[i] + a[j] + a[k] + a[l]== sum): count += 1 # Return the final count return count # Driver Code if __name__ == '__main__': # Given array arr[] arr = [ 4, 5, 3, 1, 2, 4 ] # Given sum S S = 13 N = len(arr) # Function Call print(countSum(arr, N, S)) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
class GFG{
// Function to return the number of
// quadruplets with the given sum
static int countSum(int []a, int n, int sum)
{
// Initialize variables
int i, j, k, l;
// Initialize answer
int count = 0;
// All possible first elements
for(i = 0; i < n - 3; i++)
{
// All possible second elements
for(j = i + 1; j < n - 2; j++)
{
// All possible third elements
for(k = j + 1; k < n - 1; k++)
{
// All possible fourth elements
for(l = k + 1; l < n; l++)
{
// Increment counter by 1
// if quadruplet sum is S
if (a[i] + a[j] +
a[k] + a[l] == sum)
count++;
}
}
}
}
// Return the final count
return count;
}
// Driver Code
public static void Main()
{
// Given array arr[]
int []arr = { 4, 5, 3, 1, 2, 4 };
// Given sum S
int S = 13;
int N = arr.Length;
// Function Call
System.Console.Write(countSum(arr, N, S));
}
}
// This code is contributed by SURENDRA_GANGWAR
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to return the number of
// quadruplets with the given sum
function countSum(a, n, sum)
{
// Initialize variables
let i, j, k, l;
// Initialize answer
let count = 0;
// All possible first elements
for(i = 0; i < n - 3; i++)
{
// All possible second elements
for(j = i + 1; j < n - 2; j++)
{
// All possible third elements
for(k = j + 1; k < n - 1; k++)
{
// All possible fourth elements
for(l = k + 1; l < n; l++)
{
// Increment counter by 1
// if quadruplet sum is S
if (a[i] + a[j] +
a[k] + a[l] == sum)
count++;
}
}
}
}
// Return the final count
return count;
}
// Driver Code
// Given array arr[]
let arr = [ 4, 5, 3, 1, 2, 4 ];
// Given sum S
let S = 13;
let N = arr.length;
// Function Call
document.write(countSum(arr, N, S));
</script>
Producción:
3
Complejidad de Tiempo: O(N 4 )
Espacio Auxiliar: O(1)
Mejor enfoque: para optimizar el enfoque anterior, la idea es utilizar una estructura de datos de mapa . Siga los pasos a continuación para resolver el problema:
- Inicialice la cuenta del contador con 0 para almacenar el número de cuatrillizos.
- Recorra la array dada en el rango [0, N – 3) usando la variable i . Para cada elemento arr[i] , recorra la array nuevamente sobre el rango [i + 1, N – 2) usando la variable j y haga lo siguiente:
- Encuentre el valor de la suma requerida (digamos req ) como (S – arr[i] – arr[j]) .
- Inicialice count_twice con 0 que almacenará el recuento de pares ordenados en el subarreglo anterior con sum (S – arr[i] – arr[j]) .
- Después de encontrar count_twice , actualice el conteo por count_twice / 2 .
- Después de los pasos anteriores, imprima el valor de count como resultado.
A continuación se muestra la implementación de la idea anterior:
C++
// C++ program for the above approach
#include <iostream>
#include <unordered_map>
using namespace std;
// Function to return the number of
// quadruplets having given sum
int countSum(int a[], int n, int sum)
{
// Initialize variables
int i, j, k, l;
// Initialize answer
int count = 0;
// All possible first elements
for (i = 0; i < n - 3; i++) {
// All possible second element
for (j = i + 1; j < n - 2; j++) {
int req = sum - a[i] - a[j];
// Use map to find the
// fourth element
unordered_map<int, int> m;
// All possible third elements
for (k = j + 1; k < n; k++)
m[a[k]]++;
int twice_count = 0;
// Calculate number of valid
// 4th elements
for (k = j + 1; k < n; k++) {
// Update the twice_count
twice_count += m[req - a[k]];
if (req - a[k] == a[k])
twice_count--;
}
// Unordered pairs
count += twice_count / 2;
}
}
// Return answer
return count;
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 4, 5, 3, 1, 2, 4 };
// Given sum S
int S = 13;
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
cout << countSum(arr, N, S);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to return the number of
// quadruplets having given sum
static int countSum(int a[], int n, int sum)
{
// Initialize variables
int i, j, k, l;
// Initialize answer
int count = 0;
// All possible first elements
for(i = 0; i < n - 3; i++)
{
// All possible second element
for(j = i + 1; j < n - 2; j++)
{
int req = sum - a[i] - a[j];
// Use map to find the
// fourth element
HashMap<Integer, Integer> m = new HashMap<>();
// All possible third elements
for(k = j + 1; k < n; k++)
if (m.containsKey(a[k]))
{
m.put(a[k], m.get(a[k]) + 1);
}
else
{
m.put(a[k], 1);
}
int twice_count = 0;
// Calculate number of valid
// 4th elements
for(k = j + 1; k < n; k++)
{
// Update the twice_count
if (m.containsKey(req - a[k]))
twice_count += m.get(req - a[k]);
if (req - a[k] == a[k])
twice_count--;
}
// Unordered pairs
count += twice_count / 2;
}
}
// Return answer
return count;
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int arr[] = { 4, 5, 3, 1, 2, 4 };
// Given sum S
int S = 13;
int N = arr.length;
// Function Call
System.out.print(countSum(arr, N, S));
}
}
// This code is contributed by Princi Singh
Python3
# Python3 program for the above approach
# Function to return the number of
# quadruplets having given sum
def countSum(a, n, sum):
# Initialize variables
# Initialize answer
count = 0
# All possible first elements
for i in range(n - 3):
# All possible second element
for j in range(i + 1, n - 2, 1):
req = sum - a[i] - a[j]
# Use map to find the
# fourth element
m = {}
# All possible third elements
for k in range(j + 1, n, 1):
m[a[k]] = m.get(a[k], 0) + 1
twice_count = 0
# Calculate number of valid
# 4th elements
for k in range(j + 1, n, 1):
# Update the twice_count
twice_count += m.get(req - a[k], 0)
if (req - a[k] == a[k]):
twice_count -= 1
# Unordered pairs
count += twice_count // 2
# Return answer
return count
# Driver Code
if __name__ == '__main__':
# Given array arr[]
arr = [ 4, 5, 3, 1, 2, 4 ]
# Given sum S
S = 13
N = len(arr)
# Function Call
print(countSum(arr, N, S))
# This code is contributed by ipg2016107
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to return the number of
// quadruplets having given sum
static int countSum(int []a, int n,
int sum)
{
// Initialize variables
int i, j, k;
//int l;
// Initialize answer
int count = 0;
// All possible first elements
for(i = 0; i < n - 3; i++)
{
// All possible second element
for(j = i + 1; j < n - 2; j++)
{
int req = sum - a[i] - a[j];
// Use map to find the
// fourth element
Dictionary<int,
int> m = new Dictionary<int,
int>();
// All possible third elements
for(k = j + 1; k < n; k++)
if (m.ContainsKey(a[k]))
{
m[a[k]]++;
}
else
{
m.Add(a[k], 1);
}
int twice_count = 0;
// Calculate number of valid
// 4th elements
for(k = j + 1; k < n; k++)
{
// Update the twice_count
if (m.ContainsKey(req - a[k]))
twice_count += m[req - a[k]];
if (req - a[k] == a[k])
twice_count--;
}
// Unordered pairs
count += twice_count / 2;
}
}
// Return answer
return count;
}
// Driver Code
public static void Main(String[] args)
{
// Given array []arr
int []arr = { 4, 5, 3, 1, 2, 4 };
// Given sum S
int S = 13;
int N = arr.Length;
// Function Call
Console.Write(countSum(arr, N, S));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// JavaScript program for the above approach
// Function to return the number of
// quadruplets having given sum
function countSum(a, n, sum)
{
// Initialize variables
var i, j, k, l;
// Initialize answer
var count = 0;
// All possible first elements
for (i = 0; i < n - 3; i++) {
// All possible second element
for (j = i + 1; j < n - 2; j++) {
var req = sum - a[i] - a[j];
// Use map to find the
// fourth element
var m = new Map();
// All possible third elements
for (k = j + 1; k < n; k++)
{
if(m.has(a[k]))
m.set(a[k], m.get(a[k])+1)
else
m.set(a[k], 1)
}
var twice_count = 0;
// Calculate number of valid
// 4th elements
for (k = j + 1; k < n; k++) {
// Update the twice_count
if(m.has(req - a[k]))
twice_count += m.get(req - a[k]);
if ((req - a[k]) == a[k])
twice_count--;
}
// Unordered pairs
count += parseInt(twice_count / 2);
}
}
// Return answer
return count;
}
// Driver Code
// Given array arr[]
var arr = [4, 5, 3, 1, 2, 4];
// Given sum S
var S = 13;
var N = arr.length;
// Function Call
document.write( countSum(arr, N, S));
</script>
Producción:
3
Complejidad de tiempo: O(N 3 ) donde N es el tamaño de la array dada,
Espacio auxiliar: O(N)
Enfoque eficiente: la idea es similar al enfoque anterior usando un mapa . En este enfoque, fije el tercer elemento , luego encuentre y almacene la frecuencia de las sumas de todos los dos primeros elementos posibles de cualquier cuatrillo de la array dada. Siga los pasos a continuación para resolver el problema:
- Inicialice el conteo de contadores para almacenar los cuatrillizos totales con la suma S dada y un mapa para almacenar todas las sumas posibles para los dos primeros elementos de cada cuatrillizo posible.
- Recorra la array dada en el rango [0, N – 1] usando la variable i donde arr[i] es el 3er elemento fijo .
- Luego, para cada elemento arr[i] en el paso anterior, recorra la array dada en el rango [i + 1, N – 1] usando la variable j e incremente el contador en map [arr[i] + arr[j] ] .
- Después de atravesar el ciclo anterior, para cada elemento arr[i] , recorrer la array arr[] de j = 0 a i – 1 e incrementar la frecuencia de cualquier suma arr[i] + arr[j] de los dos primeros elementos de cualquier cuatrillizo posible en 1 , es decir, incremente map[arr[i] + arr[j]] en 1 .
- Repita los pasos anteriores para cada elemento arr[i] y luego imprima el recuento del contador como el número total de cuatrillizos con la suma S dada .
A continuación se muestra la implementación de la idea anterior:
C++
// C++ program for the above approach
#include <iostream>
#include <unordered_map>
using namespace std;
// Function to return the number of
// quadruplets having the given sum
int countSum(int a[], int n, int sum)
{
// Initialize variables
int i, j, k;
// Initialize answer
int count = 0;
// Store the frequency of sum
// of first two elements
unordered_map<int, int> m;
// Traverse from 0 to N-1, where
// arr[i] is the 3rd element
for (i = 0; i < n - 1; i++) {
// All possible 4th elements
for (j = i + 1; j < n; j++) {
// Sum of last two element
int temp = a[i] + a[j];
// Frequency of sum of first
// two elements
if (temp < sum)
count += m[sum - temp];
}
for (j = 0; j < i; j++) {
// Store frequency of all possible
// sums of first two elements
int temp = a[i] + a[j];
if (temp < sum)
m[temp]++;
}
}
// Return the answer
return count;
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 4, 5, 3, 1, 2, 4 };
// Given sum S
int S = 13;
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
cout << countSum(arr, N, S);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to return the number of
// quadruplets having the given sum
static int countSum(int a[], int n, int sum)
{
// Initialize variables
int i, j, k;
// Initialize answer
int count = 0;
// Store the frequency of sum
// of first two elements
HashMap<Integer, Integer> m = new HashMap<>();
// Traverse from 0 to N-1, where
// arr[i] is the 3rd element
for(i = 0; i < n - 1; i++)
{
// All possible 4th elements
for(j = i + 1; j < n; j++)
{
// Sum of last two element
int temp = a[i] + a[j];
// Frequency of sum of first
// two elements
if (temp < sum && m.containsKey(sum - temp))
count += m.get(sum - temp);
}
for(j = 0; j < i; j++)
{
// Store frequency of all possible
// sums of first two elements
int temp = a[i] + a[j];
if (temp < sum)
if (m.containsKey(temp))
m.put(temp, m.get(temp) + 1);
else
m.put(temp, 1);
}
}
// Return the answer
return count;
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int arr[] = { 4, 5, 3, 1, 2, 4 };
// Given sum S
int S = 13;
int N = arr.length;
// Function Call
System.out.print(countSum(arr, N, S));
}
}
// This code is contributed by Princi Singh
Python3
# Python3 program for the above approach from collections import defaultdict # Function to return the number of # quadruplets having the given sum def countSum(a, n, sum): # Initialize answer count = 0 # Store the frequency of sum # of first two elements m = defaultdict(int) # Traverse from 0 to N-1, where # arr[i] is the 3rd element for i in range(n - 1): # All possible 4th elements for j in range(i + 1, n): # Sum of last two element temp = a[i] + a[j] # Frequency of sum of first # two elements if (temp < sum): count += m[sum - temp] for j in range(i): # Store frequency of all possible # sums of first two elements temp = a[i] + a[j] if (temp < sum): m[temp] += 1 # Return the answer return count # Driver Code if __name__ == "__main__": # Given array arr[] arr = [ 4, 5, 3, 1, 2, 4 ] # Given sum S S = 13 N = len(arr) # Function Call print(countSum(arr, N, S)) # This code is contributed by chitranayal
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to return the number of
// quadruplets having the given sum
static int countSum(int []a, int n, int sum)
{
// Initialize variables
int i, j;
// Initialize answer
int count = 0;
// Store the frequency of sum
// of first two elements
Dictionary<int,
int> m = new Dictionary<int,
int>();
// Traverse from 0 to N-1, where
// arr[i] is the 3rd element
for(i = 0; i < n - 1; i++)
{
// All possible 4th elements
for(j = i + 1; j < n; j++)
{
// Sum of last two element
int temp = a[i] + a[j];
// Frequency of sum of first
// two elements
if (temp < sum && m.ContainsKey(sum - temp))
count += m[sum - temp];
}
for(j = 0; j < i; j++)
{
// Store frequency of all possible
// sums of first two elements
int temp = a[i] + a[j];
if (temp < sum)
if (m.ContainsKey(temp))
m[temp]++;
else
m.Add(temp, 1);
}
}
// Return the answer
return count;
}
// Driver Code
public static void Main(String[] args)
{
// Given array []arr
int []arr = { 4, 5, 3, 1, 2, 4 };
// Given sum S
int S = 13;
int N = arr.Length;
// Function Call
Console.Write(countSum(arr, N, S));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript program for the above approach
// Function to return the number of
// quadruplets having the given sum
function countSum(a, n, sum)
{
// Initialize variables
let i, j, k;
// Initialize answer
let count = 0;
// Store the frequency of sum
// of first two elements
let m = new Map();
// Traverse from 0 to N-1, where
// arr[i] is the 3rd element
for(i = 0; i < n - 1; i++)
{
// All possible 4th elements
for(j = i + 1; j < n; j++)
{
// Sum of last two element
let temp = a[i] + a[j];
// Frequency of sum of first
// two elements
if (temp < sum && m.has(sum - temp))
count += m.get(sum - temp);
}
for(j = 0; j < i; j++)
{
// Store frequency of all possible
// sums of first two elements
let temp = a[i] + a[j];
if (temp < sum)
if (m.has(temp))
m.set(temp, m.get(temp) + 1);
else
m.set(temp, 1);
}
}
// Return the answer
return count;
}
// Driver Code
// Given array arr[]
let arr = [ 4, 5, 3, 1, 2, 4 ];
// Given sum S
let S = 13;
let N = arr.length;
// Function Call
document.write(countSum(arr, N, S));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
3
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)