subset problem

general
,
1

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 O (1) space.

2

the following code computes the required triplet value

def triple_with_sum_in_range12(nrs):

a = [n for n in nrs if 0 < n < 1]

b = [n for n in nrs if 1 <= n < 2]

min3a = max3a = a[:3]

for n in a[3:]:

min3a = sorted(min3a + [n])[:3]

max3a = sorted(max3a + [n])[1:]

if len(a) >= 3:

if 2 <= sum(min3a):

  return None

elif 1 < sum(min3a) < 2: 

  return min3a


if 1 < sum(max3a): # (*) tricky case

  for i in xrange(4):

    if 1 < sum(min3a[:i] + max3a[i:]) < 2:

      return min3a[:i] + max3a[i:]

if len(a) >= 2 and len(b) >= 1:

triple = min3a[:2] + [min(b)]

if sum(triple) < 2:

  return triple
3

@avi_raj : Could you explain your code? I have no understanding of python whatsoever.

4

https://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