Triplet whose sum in range (1,2)

Question

Given n positive real numbers in an array, find whether there exists a triplet among this set such that, the sum of the triplet is in the range (1, 2). Do it in linear time and constant space.

the array is not ordered.

numbers are positive

numbers are real numbers

Any help would be greatly appreciated. Thanks.

are there any other assumptions? like the range of the numbers? what kind of assumptions can we make about the set - is the lookup for given number constant/can we traverse it somehow? is it ordered? — Mateusz Dymczyk, Oct 24 '13 at 05:24
The triplet elements need not be consecutive (adjacent) in the list? — Abhishek Bansal, Oct 24 '13 at 05:26
This is a decision problem (i.e. it's not asking you to find such a triplet) so aggregate statistics might be useful. For example, if you find at least 3 numbers in the range (1/3, 2/3) then return true. I suspect that it's possible to define a set of buckets whose membership count can be used to answer some cases definitively and leave others to be answered with one or two more scans. — Adam, Oct 24 '13 at 05:54
@Adam you are close. The easiest ranges to use are (0,2/3), [2/3, 1], and (1,2) since you know at least one number must come from the first range and at most one number can come from the third range — Soul Ec, Oct 24 '13 at 05:56
@Trying Did they ask you to just explain your approach or did they put you in front of a screen/keyboard and asked you to solve this in a specific language? — mwhs, Oct 24 '13 at 06:06
I think it is similar to this question. http://stackoverflow.com/questions/13216416/finding-triplets-in-a-array-with-sum-within-a-range — Abhishek Bansal, Oct 24 '13 at 06:06
@AbhishekBansal please read the question properly mine is asking O(N) time and constant space algo. — Trying, Oct 24 '13 at 06:14
Check this link http://www.quora.com/Programming-Interviews/Given-n-positive-real-numbers-find-whether-there-exists-a-triplet-among-this-set-such-that-the-sum-of-the-triplet-is-in-the-range-1-2-Do-it-in-linear-time-and-constant-space — Abhishek Bansal, Oct 24 '13 at 06:22
The numbers are not real numbers. The problem just doesn't make sense if they are. They might be floating point numbers, which are often inaccurately called real numbers. — harold, Oct 24 '13 at 06:36
@harold in computational complexity theory, generally the issues with real numbers are glossed over by leveraging a real oracle — Soul Ec, Oct 24 '13 at 06:45

score 53 · Accepted Answer · edited Mar 17 '15 at 06:28

The trick is to figure out a way to categorize the possible solutions and come up with a linear-time constant-space solution for each.

Consider the three ranges X = (0,2/3), Y = [2/3,1], Z = (1,2). At most one value can come from Z (if two values came from Z, then the sum would exceed 1+1=2). Similarly, at least one value must come from X. Suppose there were 3 values a <= b <= c so that 1 <= a+b+c <= 2 . Then, consider what possible classes of solutions are feasible:

A) `a \in X, b \in X, C \in X` 
B) `a \in X, b \in X, C \in Y` 
C) `a \in X, b \in X, C \in Z` 
D) `a \in X, b \in Y, C \in Y` 
E) `a \in X, b \in Y, C \in Z`

So how can we test each case?

Case A is incredibly easy to test: the sum is guaranteed to be below 2, so we just need to test the largest sum (largest 3 elements in X) exceeds 1.

Case C is incredibly easy to test: since the sum is guaranteed to be above 1, we only need to check if the sum is below 2. So in order to do that, we just need to test the smallest 2 values in X and the smallest value in Z

Cases D and E are similar to C (since the sum must be at least 4/3 > 1, choose the smallest possible values in each class).

Case B is the only tricky case. 0 < a+b < 4/3 and 2/3 <= c <= 1. To handle case B, we consider these intervals : X1 = (0, 1/2), X2 = [1/2 2/3), Y = [2/3, 1].

This results in following three valid cases :

B1. a in X1, b in X2, c in Y

B2. a in X1, b in X1, c in Y

B3. a in X2, b in X2, c in Y

Case B1 & B3 : Sum of three numbers is always greater than 1 so we take minimum values and check if it is smaller than 2 or not.

Case B2 : Sum of three numbers is always less than 2, so we take maximum sum and check if is greater than 1 or not.

So to summarize, the tests are:

|X| >= 3 and Xmax(1) + Xmax(2) + Xmax(3) >= 1
|X| >= 2, |Z| >= 1, and Xmin(1)+Xmin(2)+Zmin(1) <= 2
|X| >= 1, |Y| >= 2, and Xmin(1)+Ymin(1)+Ymin(2) <= 2
|X| >= 1, |Y| >= 1, |Z| >= 1, and Xmin(1)+Ymin(1)+Zmin(1) <= 2
|X| >= 2, |Y| >= 1, and Xmax(1) + Xmax(2) + Ymin(1) < 2
|X| >= 2, |Y| >= 1, and Xmin(1) + Xmin(2) + Ymax(1) > 1)

Each test can be performed in linear time and constant space (you only need to find Xmax(1), Xmax(2), Xmax(3), Xmin(1), Xmin(2), Ymin(1), Ymin(2), Ymax(1), Zmin(1), all of which can be found in one pass even if the data is not sorted)

In case A, the sum is guaranteed to be below 2 (that's by definition of the ranges), so the only check is that the sum exceeds 1. That's why you only need to look at the max of the possible sums — Soul Ec, Oct 24 '13 at 06:48
In case B, you said "If the maximum sum of `a+b` is less than 1/3, then there is no possible triplet", but this seems incorrect: if `c=1` and `0 < a+b < 1/3` then you do have a triplet. Similarly, your statement about the minimum sum of a+b having to be less than 1 is not necessarily true. — interjay, Oct 24 '13 at 14:33
@interjay the third set Z is an open set `Z = (1,2)` which is why `c=1` is not possible — Soul Ec, Dec 16 '14 at 13:52
Case B states that c is from set Y, so 1 is a valid value. I don't see how set Z is relevant. Besides, my point would stand even if c = 0.999. — interjay, Dec 16 '14 at 14:23
To handle case B, we consider these intervals X1 = (0, 1/2) X2 = [1/2 2/3) Y = [2/3, 1]. This results in following cases. F) a in X1, b in X2, c in Y G) a in X1, b in X1, c in Y H) a in X2, b in X2, c in Y Case F and H are similar, sum of three numbers is always greater than 1 so we take minimum values and check if it is smaller than 2 or not. Case G, sum of three numbers is always less than 2, so we take maximum sum and check if is greater than 1 or not. — IsAs, Jan 06 '15 at 12:43
@IsAs I'm not sure if I'm understanding how case B is handled. Especially how B1 is handled. In the last two result equations, we take Xmax(1) + Xmax(2) or Xmin(1) + Xmin(2). But in case B1 we might need to take Xmin(1) + Xmax(2) because both maxes might be in X2 and both mins might be in X1. Not sure if I can come up with the corresponding counter example though. Am I missing something? — willir, Jan 07 '18 at 23:12
Can somebody explain how we reached on selecting these magic bucket range? Like in every solution I read, they first take the range, (0,2/3),(2/3,1),(1,2). Then they say one of the cases is tricky and will take (0,1/2) (1/2,2/3),(2/3 1). Can somebody explain how these buckets will change if I change the range to 3 — sebin vincent, Sep 10 '21 at 18:33

score 5 · Answer 2 · answered Jun 06 '18 at 20:33

So, you have an array of double data types of length n. Intialize three variables a,b and c as first 3 values of array.Now,iterate from i = 3 to n and check the following: 1)Check if sum falls in (1, 2),if it does then return true. 2)If not, then check if sum is greater than 2,if so, then replace MAX(a,b,c) to current element arr[i]. 3)Otherwise sum must be less than 1 then replace MIN(a,b,c) to current element arr[i].And finally after coming out of loop check once again for last triplet if sum falls in (1,2) then return true,otherwise return false.

enter code here
double a=arr[0], b=arr[1], c=arr[2];
for(int i=3 ; i<n ; i++){
    // check if sum fall in (1, 2)
    if(a+b+c > 1 && a+b+c < 2){
        return 1;
    }
    // if not, then check is sum greater than 2
    // if so, then replece MAX(a,b,c) to new number
    else if(a+b+c > 2){
        if(a>b && a>c){
            a = arr[i];
        }
        else if(b>a && b>c){
            b = arr[i];
        }
        else if(c>a && c>b){
            c = arr[i];
        }
    }
    // else then sum must be less than 1
    // then replace MIN(a,b,c) to new number
    else{
        if(a<b && a<c){
            a = arr[i];
        }
        else if(b<a && b<c){
            b = arr[i];
        }
        else if(c<a && c<b){
            c = arr[i];
        }
    }
}
// check for last a, b, c  triplet
if(a+b+c > 1 && a+b+c < 2){
    return 1;
}
else{
    return 0;
}

[0.3,0.4,1.5,0.1,0.1]. Your algorithm fails for these kind of test cases. — Kenpachi Zaraki, Sep 26 '19 at 16:18

Kapil · Answer 3 · 2020-06-14T12:37:27.633

Question asked is similar to this InterviewBit question. I've made some changes to the solution mentioned below to match exactly what you asked.

There are three conditions:

First, if the sum is between 1 and 2.
Second, if the sum is greater than 2, then the larger element of the three will be replaced with the next element and the process is repeated.
Third, if the sum is less than 1, then the smaller element of the three will be replaced with the next element and same process is repeated.

int Solution::solve(vector<float> &A) {
    if(A.size()<3) return 0;

    float a = A[0];
    float b = A[1];
    float c = A[2];

    for(int i=3;i<A.size();++i){
        if(a+b+c>1 && a+b+c<2)
            return 1;

        float temp = A[i];

        if(a+b+c>=2){
            if(a>b && a>c)
                a = temp;
            else if(b>c && b>a)
                b = temp;
            else
                c = temp;
        }
        else{
            if(a<b && a<c)
                a = temp;
            else if(b<c && b<a)
                b = temp;
            else
                c = temp;
        }
    }

    if(a+b+c>1 && a+b+c<2) return 1;

    return 0;
}

Same question can also be solved using two pointer technique. In this first we'll have to sort the array. But, It's complexity will be more than O(logn).

int Solution::solve(vector<float> &A) {
    int n = A.size();

    if(n<3) return 0;
    sort(A.begin(), A.end());

    int l = 0, r = n-1;

    while(l<r-1){
        float s = A[l]+A[l+1]+A[r];
        if(s>=2)
            r = r-1;
        else if(s<1)
            l = l+1;
        else return 1;
    }
    return 0;
}

score 3 · Answer 4 · answered Dec 08 '19 at 14:38

This problem can easily be solved in linear runtime time using the sliding window sum approach. In this case, we will use a window of size 3. This is also called the 'moving sum algorithm'.

Algorithm Below

1> Prepare the window of size 3 with the first 3 elements
2> IF (array.len <= 3): CHECK IF window-sum is in the range (1,2), then RETURN accordingly
3> FOR i = 3 UPTO (array.len-1)
3.1> SORT the window (3log3 = constant time operation)
3.2> IF window-sum is in the range (1,2): RETURN 1 or TRUE
3.3> ELSE IF window-sum < 1: Replace the smallest element in the window (window[0]) with array[i]
3.4> ELSE IF window-sum > 2: Replace the largest element in the window (window[2]) with array[i]
4> Outside the loop, check the FINAL window sum and RETURN accordingly.

Access the Python code here. Star the repository, please!

I think there is an issue with this algorithm Consider [0.2 0.2 1.7 0.5 0.05 0.05]. There are several solutions in this case and they must each use 1.7, but this algorithm would remove the number 1.7 and conclude that it is not possible to find a triplet under the given constraints. — roulette01, Sep 28 '20 at 20:54

Manish Sakariya · Answer 5 · 2019-05-10T11:56:42.700

Java code for the solution given by @soul Ec.

we need to modify the case B. let say our numbers are a+b+c

there are three ranges 
    x1        x2           y  
 (0,1/2)   (1/2,2/3)    (2/3,1)

we have 4 possibilities
1.   x1 + x1 +y
2.   x2 + x2 +y
3.   x1 + x2 +y
4    x2 + x1 +y

here case 3 and 4 are identical as sum of it will be same. so we have 3 cases only.

1.  x1 + x1 + y it is always <2         ( do x1max+x1max+ymax <2 to verify)
so we have to check if x1max(1)+x1max(2)+ymax(1) > 1
2. x2 + x2 + y it is always >1          ( do x2min+x2min+ymin >1 to verify)
so we have to check if x2min(1)+x2min(2)+ymin(1) <=2
3. x1 + x2 + y it is always >1           (do x1min+x2min+ymin >1 to verify)
so we have to check if x1min(1)+x2min(1)+ymin(1)<=2

   public static int solve(ArrayList<String> A) {

      double d[]= new double[A.size()];
      for(int i=0;i<A.size();i++) {
          d[i]= Double.parseDouble(A.get(i));
      }


       double range1 = 0;
       double range2 = (double) 2/3;
       double range3 = 1;
       double range4 = 2;

       double range02 =(double) 1/2;

       // min and max in range (0,2/3)
       double min1= Double.MAX_VALUE;
       double min2=Double.MAX_VALUE;
       double min3=Double.MAX_VALUE;

       double max1= Double.MIN_VALUE;
       double max2=Double.MIN_VALUE;
       double max3=Double.MIN_VALUE;

       // min and max in range (2/3,1)
       double miny1= Double.MAX_VALUE;
       double miny2=Double.MAX_VALUE;
       double miny3=Double.MAX_VALUE;


       double maxy1= Double.MIN_VALUE;
       double maxy2=Double.MIN_VALUE;
       double maxy3=Double.MIN_VALUE;

       // min and max in range (1,2)
       double minz1= Double.MAX_VALUE;
       double minz2=Double.MAX_VALUE;
       double minz3=Double.MAX_VALUE;

       double maxz1= Double.MIN_VALUE;
       double maxz2=Double.MIN_VALUE;
       double maxz3=Double.MIN_VALUE;

        // min and max in range (0,1/2)
       double minxx1= Double.MAX_VALUE;
       double minxx2=Double.MAX_VALUE;
       double minxx3=Double.MAX_VALUE;

       double maxx1= Double.MIN_VALUE;
       double maxx2=Double.MIN_VALUE;
       double maxx3=Double.MIN_VALUE;

       // min and max in range (1/2,2/3)
       double minyy1= Double.MAX_VALUE;
       double minyy2=Double.MAX_VALUE;
       double minyy3=Double.MAX_VALUE;

       double maxyy1= Double.MIN_VALUE;
       double maxyy2=Double.MIN_VALUE;
       double maxyy3=Double.MIN_VALUE;




    for (int i = 0; i < d.length; i++) {
        if (d[i] >= range1 && d[i] < range02) {
            if (d[i] < minxx3) {
                minxx1=minxx2;
                minxx2=minxx3;
                minxx3 = d[i];


            } else if (d[i] > minxx3 && d[i] < minxx2) {
                minxx1=minxx2;
                minxx2 = d[i];

            } else if (d[i] > minxx3 && d[i] > minxx2 && d[i] < minxx1) {
                minxx1 = d[i];
            }

            if (d[i] > maxx3) {
                maxx1=maxx2;
                maxx2=maxx3;
                maxx3 = d[i];
            } else if (d[i] < maxx3 && d[i] > maxx2) {
                maxx1=maxx2;
                maxx2 = d[i];
            } else if (d[i] < maxx3 && d[i] < maxx2 && d[i] > maxx1) {
                maxx1 = d[i];
            }


        }

        if (d[i] >= range02 && d[i] < range2) {
            if (d[i] < minyy3) {
                minyy1=minyy2;
                minyy2=minyy3;
                minyy3 = d[i];


            } else if (d[i] > minyy3 && d[i] < minyy2) {
                minyy1=minyy2;
                minyy2 = d[i];

            } else if (d[i] > minyy3 && d[i] > minyy2 && d[i] < minyy1) {
                minyy1 = d[i];
            }

            if (d[i] > maxyy3) {
                maxyy1=maxyy2;
                maxyy2=maxyy3;
                maxyy3 = d[i];
            } else if (d[i] < maxyy3 && d[i] > maxyy2) {
                maxyy1=maxyy2;
                maxyy2 = d[i];
            } else if (d[i] < maxyy3 && d[i] < maxyy2 && d[i] > maxyy1) {
                maxyy1 = d[i];
            }


        }


        if (d[i] >= range1 && d[i] < range2) {
            if (d[i] < min3) {
                min1=min2;
                min2=min3;
                min3 = d[i];


            } else if (d[i] > min3 && d[i] < min2) {
                min1=min2;
                min2 = d[i];

            } else if (d[i] > min3 && d[i] > min2 && d[i] < min1) {
                min1 = d[i];
            }

            if (d[i] > max3) {
                max1=max2;
                max2=max3;
                max3 = d[i];
            } else if (d[i] < max3 && d[i] > max2) {
                max1=max2;
                max2 = d[i];
            } else if (d[i] < max3 && d[i] < max2 && d[i] > max1) {
                max1 = d[i];
            }


        }

        if (d[i] >= range2 && d[i] < range3) {
            if (d[i] < miny3) {
                miny1=miny2;
                miny2=miny3;
                miny3 = d[i];


            } else if (d[i] > miny3 && d[i] < miny2) {
                miny1=miny2;
                miny2 = d[i];

            } else if (d[i] > miny3 && d[i] > miny2 && d[i] < miny1) {
                miny1 = d[i];
            }

            if (d[i] > maxy3) {
                maxy1=maxy2;
                maxy2=maxy3;
                maxy3 = d[i];
            } else if (d[i] < maxy3 && d[i] > maxy2) {
                maxy1=maxy2;
                maxy2 = d[i];
            } else if (d[i] < maxy3 && d[i] < maxy2 && d[i] > maxy1) {
                maxy1 = d[i];
            }


        }


        if (d[i] >= range3 && d[i] <= range4) {
            if (d[i] < minz3) {
                minz1=minz2;
                minz2=minz3;
                minz3 = d[i];


            } else if (d[i] > minz3 && d[i] < minz2) {
                minz1=minz2;
                minz2 = d[i];

            } else if (d[i] > minz3 && d[i] > minz2 && d[i] < minz1) {
                minz1 = d[i];
            }

            if (d[i] > maxz3) {
                maxz1=maxz2;
                maxz2=maxz3;
                maxz3 = d[i];
            } else if (d[i] < maxz3 && d[i] > maxz2) {
                maxz1=maxz2;
                maxz2 = d[i];
            } else if (d[i] < maxz3 && d[i] < maxz2 && d[i] > maxz1) {
                maxz1 = d[i];
            }


        }




       }

    if(max1+max2+max3>=1 && max1!=Double.MIN_VALUE && max2!=Double.MIN_VALUE && max3!=Double.MIN_VALUE) 
        return 1;

    if(min3+min2+minz3<=2 && min3!=Double.MAX_VALUE && min2!=Double.MAX_VALUE && minz3!=Double.MAX_VALUE ) 
        return 1;

    if(min3+miny3+miny2<=2 && min3!=Double.MAX_VALUE && miny3!=Double.MAX_VALUE && miny2!=Double.MAX_VALUE)
       return 1;
    if(min3+miny3+minz3<=2 && min3!=Double.MAX_VALUE && miny3!=Double.MAX_VALUE && minz3!=Double.MAX_VALUE)
        return 1;

    if(maxx3+maxx2+maxy3>1 && maxx3!=Double.MIN_VALUE && maxx2!=Double.MIN_VALUE && maxy3!=Double.MIN_VALUE) {
        return 1;

    }

    if(minyy3+minyy2+miny3<=2 && minyy3!=Double.MAX_VALUE && minyy2!=Double.MAX_VALUE && miny3!=Double.MAX_VALUE) {
        return 1;
    }
    if(minxx3+minyy3+miny3<=2 && minxx3!=Double.MAX_VALUE && minyy3!=Double.MAX_VALUE && miny3!=Double.MAX_VALUE) {
        return 1;
    }




    return 0;






    }

score 0 · Answer 6 · answered Jul 15 '19 at 13:49

the solution is in c++(interviewbbit solution)

int Solution::solve(vector<string> &arr) {
int n=arr.size(),i;
vector<float>v;
for(i=0;i<n;i++)
{
    v.push_back(stof(arr[i]));
}
float a=v[0],b=v[1],c=v[2];

float mx=0;
for(i=3;i<n;i++)
{
    if(a+b+c<2 && a+b+c>1)
        return 1;
    else if(a+b+c>2)
    {
        if(a>b && a>c)
            a=v[i];
        else if(b>a && b>c)
            b=v[i];
        else
            c=v[i];
    }
    else
    {
        if(a<b && a<c)
            a=v[i];
        else if(b<a && b<c)
            b=v[i];
        else
            c=v[i];

    }
}
if(a+b+c>1 && a+b+c<2)
    return 1;
else
    return 0;
}

score -3 · Answer 7 · answered Oct 04 '19 at 14:24

-3

We can easily do it in O(n) , we just need to find three minimum positive real numbers ,which we can find in one iteration and in the end if their summation lies in between (1,2) then return 1 else return 0.

answered Oct 04 '19 at 14:24

Pamit Kumar Singh

1

1

This is wrong, let's say we have an array [0.2, 0.2,0.2, 0.9]. then minimum three are <1 but 1<0.2+0.2+0.9<2. – Pratik Oct 15 '19 at 15:45

score -7 · Answer 8 · edited May 23 '17 at 12:02

-7

The problem in its whole as stated is undecidable. This is due to the fact that for any two real numbers a and b it cannot be decided if a > b holds (also see this answer of me). But you have to do at least one comparison of a real number against an integer value to solve that problem. Comparing against an integer doesn't make the problem easier since you could have a real number which is 2,00...001 where there is an arbitrary number of zeros between the digits 2 and 1 which you don't know beforehand. Storing such real numbers (probably not every one, but many of them) in the main memory of a computer is not a big problem for such specific ones, since they can be represented by an approximation algorithm.

for further information I suggest reading Complexity Theory of Real Functions

edited May 23 '17 at 12:02

Community

1
1

answered Oct 24 '13 at 06:31

SpaceTrucker

13,377
6
60
99

3

By "real number" I think it means that you shouldn't be optimizing for the data representation. In terms of theory, imagine you were given an oracle that performed the calculations on real numbers -- that way, you can actually discuss the operation count and analyze performance without getting bogged down by dedekind cuts and the ilk – Soul Ec Oct 24 '13 at 06:34
"This is due to the fact that for any two real numbers a and b it cannot be decided if a > b holds" - this is a theoretical concern but doesn't hold true in any practical context. Your "real" numbers will always be limited in precision due to machine constraints, e.g. bit width for floating point numbers and memory size for custom arbitrary-precision decimal implementations. Thus it is always decidable in at least linear time if `a < b` is true for any two given numbers `a` and `b`. – l4mpi Nov 10 '13 at 21:20
1

@l4mpi We don't know if this is a theoretical concern. From the question it is only known that this was an interview. If it was an interview at wolfram research for example than you might do good in keeping such thoughts in mind. – SpaceTrucker Nov 11 '13 at 08:17
No, you misunderstood me - what you're addressing is a problem of mathematic theory (and thus of theoretical CS), but we _know_ it is irellevant in any practical CS context. This is clear by reading the question: We are _given_ some real numbers (in an array, even) which we can certainly assume to be represented in a finite way, be it as decimals/fractions/floats/whatever; thus they're orderable in finite time. Any other interpretation would be a trick question, e.g. we could also assume that `n` is so huge that we can't even look at all numbers before the heat death of the universe. – l4mpi Nov 11 '13 at 12:25
Also, if your interpretation would be true, it would be just as impossible to __sum__ two numbers in finite time which would make the whole question absurd. Furthermore, we _know_ this is a practical CS problem and not a math problem, because OP posted it here and not at the math SE (and if this were a math problem it would be off-topic here). – l4mpi Nov 11 '13 at 12:31
While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. – Josh Burgess Jan 13 '15 at 18:03
@JoshBurgess The link refers to a complete book on the topic of real numbers and complexity theory. This is only a suggestion for further reading and therefore your deletion reason doesn't apply, as the point the answer made is already included in the first part of the answer. – SpaceTrucker Jan 14 '15 at 06:07
Bah, technically we can imagine that we define a number by a pair, an initial value u0 and a function un=f( unMinus1 , n ), where u0,un and unMinus1 are taken in another set of numbers (rationals for example). The number would be defined by the limit n->inf un... Then we take u0=0, f(unMinus1,n)=unMinus1+9/10^n and we try to compare this number to 1... This is perfectly representable in computer, but hard to compare, even if off-topic! – aka.nice Sep 29 '20 at 20:48

Triplet whose sum in range (1,2)

8 Answers8

Linked