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'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 3

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 4

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 5

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 6

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 7

What you want is a selection algorithm if you work with non-fixed number of values.

However, if your code only needs to check three values, you should avoid loops and specific algorithms, and just concentrace on micro-optimizations — specifically, as little branching as possible.

There is some stuff about this in Hacker's Delight, chapter 4, where you can typecast your signed integer to unsigned to halve the number of branches. This is done in the function smallest_v2() in the C-code below:

#include <stdio.h>
#include <limits.h>

int smallest_v1(int a, int b, int c)
{
        int min = INT_MAX;

        min = a>0 && a<min ? a : min;
        min = b>0 && b<min ? b : min;
        min = c>0 && c<min ? c : min;
}

// See Hacker's Delight, chapter 4.
int smallest_v2(int a, int b, int c)
{
        int min = INT_MAX;

        if ( (unsigned) a < min ) min = a;
        if ( (unsigned) b < min ) min = b;
        if ( (unsigned) c < min ) min = c;

        return min;
}

int main()
{
        printf("min v1: %d\n", smallest_v1(-10, 7, 3));
        printf("min v2: %d\n", smallest_v1(-10, 7, 3));
}

Basically, the book says that if you want to check if

1 <= i <= 10

then this is the same as doing an unsigned comparison

(unsigned)(i - 1) <= 9

The book also offers a proof. What you get is better branch prediction in your code. You should make a test program and time it.

Answer 8

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 9

Hard to believe Delphi is still limited to two values in the Min function. :-(

In Python you could set up a function to work with any number of arguments like this:

def PosMin(*numbers):
    try:
        return min(num for num in numbers if num > 0)
    except:
        return 0

Unfortunately the "min" function raises an exception if it ends up with no values (e.g. an empty list or in this case no numbers > 0) so the exception has to be caught. There's a proposal for the next version of python to add a sentinel value and it looks like it's going to be accepted. In that case, the code would have just been

return min (num for num in numbers if num > 0, sentinel=0)

with no need for the exception handling.

Answer 10

function MinPositive(const AIntegers: array of Integer): Integer;
var
  LoopI: Integer;
  LFirstPositivePos: Integer;
begin
  Result := 0;
  LFirstPositivePos := MaxInt;
  for LoopI := Low(AIntegers) to High(AIntegers) do
  begin
    if (AIntegers[LoopI] > 0) then
    begin
      Result := AIntegers[LoopI];
      LFirstPositivePos := LoopI;
      Break;
    end;
  end;

  for LoopI := LFirstPositivePos to High(AIntegers) do
  begin
    if (AIntegers[LoopI] > 0) and (AIntegers[LoopI] < Result) then
    begin
      Result := AIntegers[LoopI];
    end;
  end;
end;

function MinPositive3(const I1, I2, I3: Integer): Integer;
begin
  Result := MinPositive([I1, I2, I3]);
end;

Answer 11

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 12

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 13

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 14

//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 15

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 16

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 17

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 18

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 19

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]

Answer 20

• 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 21

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.Select(v => (int?)v)
      .Where(v => v > 0)
      .Min() ?? 0;

returns the smallest positive value in values if one exists otherwise it returns 0. Here, I'm exploiting the fact that Enumerable.Min(IEnumerable<int?>) will return null if the sequence is empty. So, we filter out the non-positive values, and then find the minimum. If all the values are non-positive, we obtain zero as desired and otherwise find the minimum of the positive values.