Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Given an array of sorted integers, how can I find if there exists a set of 3 elements that sum to K? [duplicate]

So say I have a sorted array:

{ 1, 2, 3, 4, 5, 6 }

And I want to see if there exists three elements that sum to 14.

3 + 5 + 6 = 14

I'm pretty sure there is no way to do this in O(N) time, but I think it can be done in O(N^2) somehow.

like image 580
user3505029 Avatar asked Apr 07 '14 07:04

user3505029


People also ask

How do you find the triplet sum of an array?

Algorithm: Given an array of length n and a sum s. Create three nested loop first loop runs from start to end (loop counter i), second loop runs from i+1 to end (loop counter j) and third loop runs from j+1 to end (loop counter k) The counter of these loops represents the index of 3 elements of the triplets.

How do you find the common elements in three sorted arrays code in Python?

A simple solution is to first find intersection of two arrays and store the intersection in a temporary array, then find the intersection of third array and temporary array. Time complexity of this solution is O(n1 + n2 + n3) where n1, n2 and n3 are sizes of ar1[], ar2[] and ar3[] respectively.


2 Answers

This problem is similar to the 3SUM problem and it can done in O(N^2) . This java working code accomplishes this.

    // The function prints the values if there exists 3 distinct indices
    // in the array arr that sum to req.
    void run(){
        int[] arr = { 1, 2, 3, 4, 5, 6 };
        int req = 14;

        // For the algorithm to work correctly, the array must be sorted
        Arrays.sort(arr);      

        for(int i=0; i<arr.length; i++){// Iterate over the elements of the array.

            // Check in linear time whether there exists distinct indices 
            // lo and hi that sum to req-arr[i]
            int lo=0, hi = arr.length-1;
            boolean found = false;
            while(lo<hi){
                if(lo==i){
                    lo++;
                    continue;
                }
                if(hi==i){
                    hi--;
                    continue;
                }
                int val = arr[lo] + arr[hi] + arr[i];
                if(val == req){
                    System.out.println(arr[lo] + " + " + arr[hi] + " + " + arr[i] + " = " + req);
                    found = true;
                    break;
                }else if(val < req){
                    lo++;
                }else{
                    hi--;
                }
            }
            if(found)break;
        }
    }
like image 141
Nikunj Banka Avatar answered Oct 04 '22 08:10

Nikunj Banka


In Computational theory, this is known as 3sum problem. Best solution for this problem found so far costs O(N^2). It is still an open question whether this can be solved with better cost. You can find one implementation of this algorithm here.

like image 31
Mohit Jain Avatar answered Oct 04 '22 07:10

Mohit Jain