Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created March 15, 2018 04:09
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/4155fab43ffc9f6ccbe20ee9d57fb6d1 to your computer and use it in GitHub Desktop.
Save jianminchen/4155fab43ffc9f6ccbe20ee9d57fb6d1 to your computer and use it in GitHub Desktop.
4 sum algorithm - Give out code review for peer's code - the code has some issues, brute force solution has some issues.
#include <stdio.h>
#include <stdlib.h>
int do_findArrayQuadruplet(int *arr, int *out, size_t arrLength, int s, int i, int j, int k, int l)
{
int sum, ret = 0;
if (arrLength < 4)
return 0;
if (!arr || !out)
return 0;
sum = arr[i]+arr[j]+arr[k]+arr[l];
if (sum == s) { // Sort out
out[0] = arr[i];
out[1] = arr[j];
out[2] = arr[k];
out[3] = arr[l];
return 1;
}
if (i < arrLength)
ret = do_findArrayQuadruplet(arr, out, arrLength, s, i+1, j, k, l); // i, j, k, l
if (!ret && j < arrLength)
ret = do_findArrayQuadruplet(arr, out, arrLength, s, i, j+1, k, l);
if (!ret && k < arrLength)
ret = do_findArrayQuadruplet(arr, out, arrLength, s, i, j, k+1, l);
if (!ret && l < arrLength)
ret = do_findArrayQuadruplet(arr, out, arrLength, s, i, j, k, l+1);
return ret;
}
void findArrayQuadruplet(int const *arr, int* out, size_t arrLength, int s) {
// your code goes here
/*
take first 4 no check if sum is s
idx_1, idx_2 , idx_3 idx_4
*/
if (arrLength < 4)
return;
if (!arr || !out)
return;
if (do_findArrayQuadruplet(arr, out, arrLength, s, 0, 1, 2, 3))
sort(out, 4);
}
int main() {
return 0;
}
// sort the array ascending order
sort(arr);
// four for loops -> O(n^3) -> brute force first two numbers, first <= second
// last two numbers with given sum, 4sum - first two number's
// two sum -> two pointer technique , line 27 spent O(n^2), line 28, O(n), in total O(n^3)
// 1, 2, 3, 4, 5, 6, 7, 8, 9
// find two numbers with given 11,
// 1, 9 = 10 < 11
// 1 -> 2, 9 = 11 > 10
for(int i = 0; i < len; i++)
for(int j = i + 1; j < len; j++)
for(int k = j + 1; k < len; k++)
for(int l = k + 1; l < len; l++)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment