Dados cuatro arreglos A[], B[], C[], D[] y un entero K. La tarea es encontrar el número de combinaciones de cuatro índices únicos p, q, r, s tales que A[p] + segundo[q] + C[r] + re[s] ≤ K .
Ejemplos:
Entrada: A = {2, 3}, B = {5, 2}, C = {0}, D = {1, 2}, K = 6
Salida: 3
Explicación: Las siguientes son las combinaciones requeridas:
{2, 2, 0, 1}, {2, 2, 0, 2}, {3, 2, 0, 1}Entrada: A = {1, 1}, B = {0}, C = {0}, D = {0}, K = 1
Salida: 2
Enfoque ingenuo: la fuerza bruta sería construir la suma de todas las combinaciones de cuatro números, utilizando cuatro bucles anidados, y contar cuántas de esas sumas son como máximo K.
Complejidad de tiempo: O(N 4 ) donde N es el tamaño máximo entre esos cuatro arreglos
Espacio auxiliar: O(1)
Enfoque eficiente: mejore el método anterior utilizando Divide and Conque r y Binary Search . Siga los pasos que se mencionan a continuación para resolver el problema:
- Genere todas las combinaciones de pares posibles para A, B y C, D.
- Supongamos que cada arreglo tiene una longitud n, entonces tendremos dos arreglos, cada uno con una longitud n*n. Que sea merge1 y merge2 .
- Ordene uno de la array de combinación, digamos merge2.
- Itere a través de la array merge1 no ordenada y encuentre cuántos elementos de merge2 se pueden emparejar con una suma menor o igual a K . Se puede hacer fácilmente usando la búsqueda binaria.
A continuación se muestra la implementación del método anterior.
C++
// C++ to implement the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to get the number of combinations
int fourSumLessThanK(vector<int>& A, vector<int>& B,
vector<int>& C, vector<int>& D,
int K)
{
vector<int> merge1;
vector<int> merge2;
int res = 0;
for (int i : A) {
for (int j : B) {
// Merging A and B into merge1
merge1.push_back(i + j);
}
}
for (int i : C) {
for (int j : D) {
// Merging C and D into merge2
merge2.push_back(i + j);
}
}
// Sorting merge2
sort(merge2.begin(), merge2.end());
// Looping through unsorted merge1
for (int i : merge1) {
int l = 0, r = merge2.size() - 1;
int pos = -1;
// Binary search to find how many
// Element from merge2 can be paired
// With merge1 element with sum less
// Than or equal to K
while (l <= r) {
int mid = l + (r - l) / 2;
if (merge2[mid] + i <= K) {
pos = mid;
l = mid + 1;
}
else {
r = mid - 1;
}
}
// Adding the number
// Of pairs in the result
res += pos + 1;
}
return res;
}
// Driver Code
int main()
{
vector<int> A = { 2, 3 };
vector<int> B = { 5, 2 };
vector<int> C = { 0 };
vector<int> D = { 1, 2 };
int K = 6;
// Function call
cout << fourSumLessThanK(A, B, C, D, K);
return 0;
}
Java
// Java code for the above approach
import java.util.*;
class GFG {
// Function to get the number of combinations
static int fourSumLessThanK(int A[], int B[],
int C[], int D[],
int K)
{
List<Integer> merge1=new ArrayList<Integer>();
List<Integer> merge2=new ArrayList<Integer>();
int res = 0;
for (int i = 0; i < A.length; i++) {
for (int j = 0; j < B.length; j++) {
// Merging A and B into merge1
merge1.add(A[i] + B[j]);
}
}
for (int i = 0; i < C.length; i++) {
for (int j = 0; j < D.length; j++) {
// Merging C and D into merge2
merge2.add(C[i] + D[j]);
}
}
// Sorting merge2
Collections.sort(merge2);
// Looping through unsorted merge1
for (int i = 0; i < merge1.size(); i++) {
int l = 0, r = merge2.size() - 1;
int pos = -1;
// Binary search to find how many
// Element from merge2 can be paired
// With merge1 element with sum less
// Than or equal to K
while (l <= r) {
int mid = l + (r - l) / 2;
if (merge2.get(mid) + merge1.get(i) <= K) {
pos = mid;
l = mid + 1;
}
else {
r = mid - 1;
}
}
// Adding the number
// Of pairs in the result
res += pos + 1;
}
return res;
}
// Driver Code
public static void main (String[] args) {
int A[] = { 2, 3 };
int B[] = { 5, 2 };
int C[] = { 0 };
int D[] = { 1, 2 };
int K = 6;
System.out.println(fourSumLessThanK(A, B, C, D, K));
}
}
// This code is contributed by hrithikgarg03188.
Python3
# Python code for the above approach # Function to get the number of combinations def fourSumLessThanK(A, B, C, D, K): merge1=[]; merge2=[]; res = 0; for i in range(len(A)): for j in range(len(B)): # Merging A and B into merge1 merge1.append(A[i] + B[j]); for i in range(len(C)): for j in range(len(D)): # Merging C and D into merge2 merge2.append(C[i] + D[j]); # Sorting merge2 merge2.sort() # Looping through unsorted merge1 for i in range(len(merge1)): l = 0; r = len(merge2) - 1; pos = -1; # Binary search to find how many # Element from merge2 can be paired # With merge1 element with sum less # Than or equal to K while (l <= r): mid = (l +r) // 2; if (merge2[mid] + merge1[i] <= K): pos = mid; l = mid + 1; else: r = mid - 1; # Adding the number # Of pairs in the result res = res + pos + 1; return res; # Driver Code A = [ 2, 3 ]; B = [ 5, 2 ]; C = [ 0 ]; D = [ 1, 2 ]; K = 6; # Function call print(fourSumLessThanK(A, B, C, D, K)); # This code is contributed by Potta Lokesh
C#
// C# code for the above approach
using System;
using System.Collections;
class GFG {
// Function to get the number of combinations
static int fourSumLessThanK(int []A, int []B,
int []C, int []D,
int K)
{
ArrayList merge1 = new ArrayList();
ArrayList merge2 = new ArrayList();
int res = 0;
for (int i = 0; i < A.Length; i++) {
for (int j = 0; j < B.Length; j++) {
// Merging A and B into merge1
merge1.Add(A[i] + B[j]);
}
}
for (int i = 0; i < C.Length; i++) {
for (int j = 0; j < D.Length; j++) {
// Merging C and D into merge2
merge2.Add(C[i] + D[j]);
}
}
// Sorting merge2
merge2.Sort();
// Looping through unsorted merge1
for (int i = 0; i < merge1.Count; i++) {
int l = 0, r = merge2.Count - 1;
int pos = -1;
// Binary search to find how many
// Element from merge2 can be paired
// With merge1 element with sum less
// Than or equal to K
while (l <= r) {
int mid = l + (r - l) / 2;
if ((int)merge2[mid] + (int)merge1[i] <= K) {
pos = mid;
l = mid + 1;
}
else {
r = mid - 1;
}
}
// Adding the number
// Of pairs in the result
res += pos + 1;
}
return res;
}
// Driver Code
public static void Main () {
int []A = { 2, 3 };
int []B = { 5, 2 };
int []C = { 0 };
int []D = { 1, 2 };
int K = 6;
Console.WriteLine(fourSumLessThanK(A, B, C, D, K));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript to implement the above approach
// Function to get the number of combinations
const fourSumLessThanK = (A, B, C, D, K) => {
let merge1 = [];
let merge2 = [];
let res = 0;
for (let i in A) {
for (let j in B) {
// Merging A and B into merge1
merge1.push(A[i] + B[j]);
}
}
for (let i in C) {
for (let j in D) {
// Merging C and D into merge2
merge2.push(C[i] + D[j]);
}
}
// Sorting merge2
merge2.sort();
// Looping through unsorted merge1
for (let i in merge1) {
let l = 0, r = merge2.length - 1;
let pos = -1;
// Binary search to find how many
// Element from merge2 can be paired
// With merge1 element with sum less
// Than or equal to K
while (l <= r) {
let mid = l + parseInt((r - l) / 2);
if (merge2[mid] + merge1[i] <= K) {
pos = mid;
l = mid + 1;
}
else {
r = mid - 1;
}
}
// Adding the number
// Of pairs in the result
res += pos + 1;
}
return res;
}
// Driver Code
let A = [2, 3];
let B = [5, 2];
let C = [0];
let D = [1, 2];
let K = 6;
// Function call
document.write(fourSumLessThanK(A, B, C, D, K));
// This code is contributed by rakeshsahni
</script>
Producción
3
Complejidad de Tiempo: O(N 2 * logN)
Espacio Auxiliar: O(N 2 )