Skip to content

Instantly share code, notes, and snippets.

@pratik7368patil
Created July 16, 2020 11:46
Show Gist options
  • Save pratik7368patil/f5502a7414b0f3a9b0976713c67401e2 to your computer and use it in GitHub Desktop.
Save pratik7368patil/f5502a7414b0f3a9b0976713c67401e2 to your computer and use it in GitHub Desktop.
Four sum problem solution (4sum)
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int getSum(int arr[],int N, int K) {
for(int i=0; i < N; i++){
if(i > 0 && arr[i] == arr[i+1]) {
continue;
}
for(int j=i+1; j<N; j++) {
if(j > 0 && arr[j] == arr[j+1]) {
continue;
}
int l = j+1;
int r = N-1;
while(l < r) {
int sum = arr[i] + arr[j] + arr[l] + arr[r];
if(sum == K) {
cout << arr[i] << " "<< arr[j] << " "<< arr[l] << " "<< arr[r] <<endl;
while(l < r && arr[l] == arr[l+1]) l++;
while(l < r && arr[r] == arr[r-1]) r--;
l+=1;
r-=1;
} else if(sum > K) {
r-=1;
} else {
l+=1;
}
}
}
}
return 0;
}
int main() {
int N;
cin >> N;
int K;
cin >> K;
int arr[N];
for(int i=0; i<N; i++) {
cin >> arr[i];
}
sort(arr, arr + N);
if(N < 4) {
cout <<" "<<endl;
} else {
getSum(arr, N, K);
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment