Find the Minimum Positive Value

Question

What's the best algorithm to find the smallest non zero positive value from a fixed number (in this case 3) of values or return 0 if there are no positive questions?

My naive approach is below (in Delphi, but feel free to use whatever you like), but I think there's a more elegant way.

value1Temp := MaxInt;
value2Temp := MaxInt;
value3Temp := MaxInt;

if ( value1T > 0) then
  value1Temp := value1;
if ( value2 > 0) then
  value2Temp := value2;
if ( value3 > 0) then
  value3Temp  := value3;

Result := Min(value1Temp, Min(value2Temp, value3Temp));
if Result = MaxInt then
  Result := 0;

Edit: Sorry added what's needed if there are no positive numbers. I thought I had it in there before, but must have missed it.

Answer 1

I'd do a little loop (This is in C, I'm not a Delphi guy):

int maxPositiveValue(int *number, int listSize)
{
    int i, result = 0;

    for(i = 0; i < listSize; i++)
    {
        if(number[i] > 0 && (number[i] < result || result == 0))
            result = number[i];
    }

    return result;
}

The advantage of this code is that it is very readable and can easily be scaled to cope with any length list of values.

UPDATE: I have changed the code in response to the comments I have received below.

This new code is a little more complex but it will now handle:

1. The case where the list contains no positive integers (returns 0).
2. The case where the list contains one or more occurences of INT_MAX.
3. A list of any length.

Answer 2

I agree with Adam. You're not really going to do faster than a linear search algorithmically, if you only need the smallest natural number in a container.

His code should run pretty fast, it would most likely translated to a CMOV in x86, so the if statement inside the for loop won't cost that much anyways.

If you're going to end up wanting all the non-zero numbers in order, then of course it would be much better to sort, and then splice.

Answer 3

Result := Min(IfThen(Value1 > 0, Value1, MAXINT), 
              Min(IfThen(Value2 > 0, Value2, MAXINT),
                  IfThen(Value3 > 0, Value3, MAXINT)));

A loop won't work if the inputs aren't a list/array, per the question.

It's not clear from the question what the function should do if none of the three are positive and non-zero.

Answer 4

• Go through the values of the list, discarding them until you find a positive value, set min-value to it
• Go through the values in the rest of the list
  • If 0 < current-value < min-value, set min-value to current-value
• return min-value

Answer 5

This works no matter what the type of the array's elements is

template <typename T>
T min_pos(T* a, int n)
{
    int i /* = 0 */ /* Edit: commented this out */;

    // Find the first positive element in the array
    for (i = 0; i < n; ++i)
        if (a[i] > 0)
            break;

    // If no positive element was found, return 0
    if (i == n)
        return 0;

    T res = a[i];

    // Search the rest of the array for an element
    // that is positive yet smaller than res
    for (++i; i < n; ++i)
    {
        if ((a[i] > 0) && (a[i] < res))
            res = a[i];
    }

    return res;
}

Answer 6

This is C#

public int GetSmallestPositive(IList<int> pValues)
{
    if(pValues == null)
    {
        throw new ArgumentNullException("pValues");
    }
    int _negNumCount = 0;
    int _smallest = int.MaxValue;
    for(int i = 0; i < pValues.Count; ++i)
    {
        if(pValues[i] < _smallest)
        {
            if(pValues[i] <= 0)
            {
                ++_negNumCount;
                continue;
            }
            _smallest = pValues[i];
            if(_smallest == 1)
            {
                return 1;
            }
        }
    }
    return (_negNumCount == pValues.Count) ? 0 : _smallest;
}

In this case, and in your example, I'm using ints, so 1 is the smallest non-zero number. As long as you put your ints into a list, it will work for as many values as you want.

Edit: Fixed to return 0 if the list is full of negative numbers. Throw exception if pValues is null.

Answer 7

//return the smallest non-zero positive number, or null.
//relying on Min or Max is considered cheating.
public static int? smallestNonZeroPositiveNumberOfThree(
    int val1, int val2, int val3)
{
    //we have no guarantee that any of the 3 inputs will be positive
    int? result = null;
    if (val1 > 0) 
    {
        result = val1; 
        if (val2 > 0 && val2 < result) { result = val2; }
        if (val3 > 0 && val3 < result) { result = val3; }
    }
    else if (val2 > 0)
    {
        result = val2; 
        if (val3 > 0 && val3 < result) { result = val3; }
    }
    else if (val3 > 0)
    {
        result = val3; 
    }
    return result;
}

Answer 8

A c# version that covers all the bases (i think):

public int GetMinimumPositiveValue(IEnumerable<int> values)
{
    int result = int.MaxValue;
    bool hasPositiveValue = false;

    foreach (int value in values)
    {
        if(value == 1) { return value; } 

        if(value > 0)
        {
            hasPositiveValue = true;

            if(value < result)
            {
                result = value;
            }
        }
    }

    return hasPositiveValue ? result : 0;
}

Answer 9

Here's what I came up with after thinking about it a bit more

Result := 0;
if value1 > 0 then
  Result := value1;
if (value2 > 0) and ((Result = 0) or (value2 < Result)) then
  Result := value2;
if (value3 > 0) and ((Result = 0) or (value3 < Result)) then
  Result := value3;

Granted if you have a list, the more generic algorithms are better.

Answer 10

I see way too many lines of codes for those trying to solve the general problem in C#. If values is an IEnumerable<int> then

values.Min(r => r > 0 ? r : Int32.MaxValue)

returns the smallest positive value in values if one exists otherwise it returns Int32.MaxValue.

Answer 11

I'd do this:

Result := MaxInt;
if value1 > 0 then Result := min(Result, value1);
if value2 > 0 then Result := min(Result, value2);
if value3 > 0 then Result := min(Result, value3);
if Result = MaxInt then Result := 0;

If you want it in a loop with an arbitrary number of questions, then:

Result := MaxInt;
for I := 1 to N do
   if value[I] > 0 then Result := min(Result, value[I]);
if Result = MaxInt then Result := 0;

If you want the value array to be zero-based, change the for loop to be: 0 to N-1

I think this code makes it very clear exactly what is being done.

Putting the "then" statements on the same line makes the code look cleaner in this simple case, but feel free to indent the "then" statements onto the next line if you feel it's necessary.

Answer 12

Here's a C version riffing off of the solution in the question post, but fixes the case where all of the values are MaxInt...

int foo(int value1, int value2, int value3)
{
    int value1Temp, value2Temp, value3Temp, tempMax;
    value1Temp = max(value1, 0);
    value2Temp = max(value2, 0);
    value3Temp = max(value3, 0);
    tempMax = value1Temp | value2Temp | value3Temp;
    if (value1Temp == 0) { value1Temp = tempMax; }
    if (value2Temp == 0) { value2Temp = tempMax; }
    if (value3Temp == 0) { value3Temp = tempMax; }
    return min(value1Temp, min(value2Temp, value3Temp));
}

It's also possible to do this in a branch-free way, since min and max can be implemented as branch-free operations:

int min(int x, int y)
{
    return y + ((x - y) & -(x < y));
}

int max(int x, int y)
{
    return x - ((x - y) & -(x < y));
}

int foo(int value1, int value2, int value3)
{
    int value1Temp, value2Temp, value3Temp, tempMax, mask;
    value1Temp = max(value1, 0);
    value2Temp = max(value2, 0);
    value3Temp = max(value3, 0);
    tempMax = value1Temp | value2Temp | value3Temp;
    mask = -(value1Temp > 0);
    value1Temp = (value1Temp & mask) | (tempMax & ~mask);
    mask = -(value2Temp > 0);
    value2Temp = (value2Temp & mask) | (tempMax & ~mask);
    mask = -(value3Temp > 0);
    value3Temp = (value3Temp & mask) | (tempMax & ~mask);
    return min(value1Temp, min(value2Temp, value3Temp));
}

For more background on why you'd ever want to do this, see: Is "If" Expensive? and Bit Twiddling Hacks.

Edit: Clobbered my earlier attempt at a branch-free solution, which didn't actually work. Added a new branch-free solution which should work.

Answer 13

A slight improvement on Jason's suggestion that correctly handles empty collections and collections containing only negative values:

values.Min(r => r > 0 ? r : (int?)null) ?? 0

Answer 14

How about the following function (in Delphi of course):

function LowestPositiveInt(IntArr : array of Integer):Integer;
var
  iX : integer;
  bValid : boolean;
begin
  Result := MaxInt;
  bValid := False;
  for ix := 0 to High(IntArr) do
    if (IntArr[ix] > 0) then
      begin
        bValid := true;
        if (IntArr[iX] < Result) then
          Result := IntArr[ix];
      end;
  if not bValid then
    Result := 0;
end;

then call it like the following:

ShowMessage(IntToStr( LowestPositiveInt([5,2,3,-1,12]) ));

This should return 2. The advantage of this approach is that the array can take any number of items, including integer variables...so using your example above you could say:

Result := LowestPositiveInt( [ Value1, Value2, Value3 ] );

EDIT Updated to handle the LowestPosititiveInt( [ MaxInt, MaxInt, MaxInt ] ) scenario.

Answer 15

I don't know Delphi, but here's a quick solution in Ruby (Assume the numbers are in a list)

[1,2,42,-12].delete_if{|n| n <= 0 }.min || 0

Algorithmically, you delete all the negative (or 0) elements, then you find the minimum. If there are no positive elements, [].min returns nil, so the final || 0 gives the requested '0' as an answer.

Answer 16

Are you looking for aesthetics or speed?

If the latter, I cannot think of a way you could perform this test enough times to be detectable in an application: it just doesn't matter.

Cheers

Answer 17

In DELPHI -- if your domain is the integers, and if you can fit your args into longints, and if you can avoid passing the minimum integer ($80000000), then this will give you the result you want without any conditional branching:

function cmMinInt( XX, YY, ZZ : longint ) : longint;
begin
   result := max(0,longint(
   min(longint((XX-1) xor $80000000),
   min(longint((YY-1) xor $80000000),
   longint((ZZ-1) xor $80000000)
   )) xor $80000000)+1);
end;

The technique depends on a reversable lossless remapping of the longint type so that the range we're interested in -- the integers from 1 to MAXINT -- remain in order and occupy the lowest values. Simply toggling the sign bit almost gives what we need, except we don't want 0 included in the lower range. Subtracting 1 first (and adding it back later) fixes that. The xor operation used here widens both operands to int64, which requires an explicit cast back to longint so the min function will produce the correct result. Finally, if the operands are all neg, the minimum will be found in the upper range, and the answer will be neg. In this case we want the answer to be 0, so we simply clip it with the max function.

Here's the same math spread out over multiple statements for easier reading:

function cmMinInt( XX, YY, ZZ : longint ) : longint;
begin
   // swap ordinal coding for range MININT..0 with range 1..MAXINT
   XX := XX-1;             // move region division to between 0 and 1
   XX := XX xor $80000000; // swap regions, preserving ordering
   XX := longint(XX);      // cram back into signed 32-bit
   // similarly with YY and ZZ
   YY := longint((YY-1) xor $80000000);
   ZZ := longint((ZZ-1) xor $80000000);
   // find min of three recoded values
   result := min(XX,min(YY,ZZ));
   // swap ordering back again
   result := result xor $80000000;  // swap regions, preserving ordering
   result := result+1;              // move region division back home
   result := longint(result);       // cram back into signed 32-bit
   // if all three were neg, result at this point is neg -- clip to zero
   result := max(0,result);
end;

-Al.

Answer 18

In Haskell, as usual, its easiest to solve the general problem and then declare a special case.

foo xs = let xs1 = filter (>0) xs in if null xs1 then 0 else minimum xs1

foo3 x1 x2 x3 = foo [x1, x2, x3]