Hello again everyone. It has been quite a while since I last wrote something. Well work and life have been busy lately. Therefore I have not had much time for blogging coding fun. Anyhow, we are going to try to solve Four Sum in PHP today. And in case you were wondering… no it does not have a sexual connotation (oops).
What does four sum mean? Well we need to find four numbers (hence the name four sum) – a, b, c, d in an array such that a+b+c+d=target, where target is a given number. K-sum problems can be quite a pain as usually their brute-force solution will be O(n^k). From this excellent post on StackExchange we can get the following 2 generalized algorithms.
For even k: Compute a sorted list S of all sums of k/2 input elements. Check whether S contains both some number x and its negation −x. The algorithm runs in O(nk/2logn) time.
For odd k: Compute the sorted list S of all sums of (k−1)/2 input elements. For each input element a, check whether S contains both x and a−x, for some number x. (The second step is essentially the O(n2)-time algorithm for 3SUM.) The algorithm runs in O(n(k+1)/2) time.
For more details, see: Nir Ailon and Bernard Chazelle. Lower bounds for linear degeneracy testing. JACM 2005.
In our case though, to solve our k-sum problem there’s one last constraint. To not repeat the different sets, we’re asked to return unique sets where a<=b<=c<=d. This sounds awfully similar to our other posts How To Find Pairs That Equal To A Specific Sum In An Array or How To Find All Triples Whose Sum Is Less Than A Number In An Array, but this time the problem has different constraints and we will try to solve a k-sum problem (Four Sum) in PHP.
Well let’s get to it then. For this I’ll write the code in PHP, just because, well I am writing more php these days and it will be fun to see myself (and yourself) write in different languages.
Four Sum in PHP – Solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
function four_sum($arr, $target) { $s_arr = sort($arr); $len = count($s_arr); $ret_val = []; for ($i = 0; $i < $len; $i++) { for ($j = $i+1; $j < $len; $j++) { $k = $j+1; $m = $len-1; while($k < $m) { $sum = $s_arr[$i] + $s_arr[$j] + $s_arr[$k] + $s_arr[$m]; if ($sum == $target) { $curr_set = [$s_arr[$i], $s_arr[$j], $s_arr[$k], $s_arr[$m]]; if (!in_array($ret_val)) { $ret_val[] = $curr_set; } $k++; $m--; } else if ($sum > $target) { $m--; } else { $k--; } } } } return $ret_val; } |
Let’s give a quick analysis on the runtime complexity. Well in worst case complexity this will run at O(n3)! so we just made an n times shortening to our brute force solution ;D.
From now on you (and me) can say we will ace that interview question on Four Sum in PHP!
Hope you guys enjoyed it… and I’ll see you guys next time ;D.
Latest posts by Ajk (see all)
- Find Median from Numbers Array - January 1, 2018
- Find Whether a Number Can Be the Sum of Two Squares - August 12, 2017
- How to Find Two Primes Whose Sum is Equal to a Number N - April 22, 2017
You can make it more optimized by using the HashMap and storing the sum of the pairs in it. and checking for the sum-pairsum.
This is the code:
public class FindTheQuadrapleInMinimumComplexity {
class Pair{
int x;
int y;
public Pair(int x,int y){
this.x = x;
this.y = y;
}
}
public void findQuadraple(int arr[],int k){
Map<Integer, LinkedList> summap = new HashMap<Integer,LinkedList>();
for(int i = 0; i < arr.length-1; i++){
for(int j = i+1; j < arr.length; j++){
int sum = arr[i]+arr[j];
if(summap.get(k-sum)!=null){
List list = summap.get(k-sum);
LinkedList res = new LinkedList();
for(Pair p: list){
if((p.x!=i)&&(p.x!=j)&&(p.y!=i)&&(p.y!=j)){
System.out.println(“(“+arr[i]+”,”+arr[j]+”,”+arr[p.x]+”,”+arr[p.y]+”)”);
}
res.add(new Pair(i,j));
}
if(summap.get(sum)!=null){
summap.get(sum).addAll(res);
}else{
summap.put(sum,res);
}
}else{
LinkedList list = new LinkedList();
list.add(new Pair(i,j));
summap.put(sum, list);
}
}
}
}
static public void main(String args[]){
FindTheQuadrapleInMinimumComplexity q = new FindTheQuadrapleInMinimumComplexity();
q.findQuadraple(new int[]{1,5,1,0,6,0}, 7);
}
}