Problem of the Day -- Smallest Integer

Smallest Integer

Congrats on making it to the final problem of the week! Today's problem is a bit tricky but will seem so obvious once you get it.

Write a function that when given 3 integers returns the smallest integer of the 3 without using any comparison operator (e.g.: >, <, ==) .

Something like "return min([1,2,3])" is cheating.

Permalink: http://problemotd.com/problem/smallest-integer/

Comments:

Anonymous - 12 years ago
int smallest_int(int x, int y, int z) { unsigned int x_s, y_s, z_s; for (x_s = x, y_s = y, z_s = z; x_s & 1; x_s >> 1, y_s >> 1, z_s >> 1) { if !(y_s & 1) return y; if !(z_s & 1) return z; } return x;

reply permalink
Zing - 12 years ago
I don't think the problem said that the integers were non-negative

reply permalink

Anonymous - 12 years ago

public static int solve(int x, int y, int z) {
    x -= Integer.MIN_VALUE;
    y -= Integer.MIN_VALUE;
    z -= Integer.MIN_VALUE;
    int result = 0;
    int buf;
    while (true) {
        try {
            buf = 1 / x;
            buf = 1 / y;
            buf = 1 / z;
        } catch (RuntimeException e) { //division by 0
            return result - Integer.MIN_VALUE;
        }
        x--;
        y--;
        z--;
        result++;
    }
}

reply permalink

Anonymous - 12 years ago
Wouldn't you get negative integer values when subtracting the smallest integer value (-2^31), meaning you add 2^31 and go negativ again?

reply permalink
Anonymous - 12 years ago
ah, yes. Technically it's an error, and the correct way is to do is 'return result + Integer.MIN_VALUE;', but due to nature of MIN_VALUE there is actually no difference between - and +.

And integer overflow you are speaking of is the idea of overriding 'negative integer' problem, and there is no problem with it.

reply permalink

Tobias Frilling - 12 years ago

(defn min2 [a b]
  (let [half-dist (/ (- a b) 2)]
    (int (- (- a half-dist)
            (Math/abs (double half-dist))))))

(defn min3 [a b c]
  (min2 a (min2 b c)))

reply permalink

Foppe - 12 years ago
```
#! /usr/bin/python
# smallest.py

def smallest(i, j):
    return (i + j) / 2 - (abs(i - j)) / 2

if __name__=='__main__':
    i = 5
    j = -7
    k = 9
    l = smallest(i, j)
    m = smallest(l, k)
    print(int(m))
```
The basic formula is (i + j) / 2 - (|i - j|) / 2 for two integers with an elegant proof: i # smallest integer i + j # largest integer (i + i + j) / 2 - (i - i + j) / 2 = i + j/2 - j/2 = i

reply permalink
Daniel - 12 years ago
public int Get(int x, int y, int z) { return ReturnMinimum(x, ReturnMinimum(y, z)); }
```
    public int ReturnMinimum(int x, int y)
    {
        return y + ((x - y) & ((x - y) >> (sizeof(int) * 8 - 1)));
    }
```
reply permalink
Len - 12 years ago
Another "cheating" solution would be to put the elements in an array and use an array sorting method then pull out the head of the array. But the array sorting method almost certainly uses comparison operators inside.

I like the compositional method above: min3 = min2(a, min2(b, c)).

To compare two integers, you can re-implement the comparison using bit-wise operators. In the following solution I'm checking first if there's a mismatch between signs. In that case, return the negative value. If there is no mismatch, we merely start with the most-significant digit and work our way to the least significant until we find a mismatch. There is a potential size-of-integer issue (ie- 32-bit vs 64-bit integers,) but I can't be bothered to fix it right now.
```
#include <stdio.h>

int min2 (int a, int b) {
    int isNeg = 0x8000;
    int x = 0x4000;
    if ((a&isNeg) && !(b&isNeg)) return a;
    else if (!(a&isNeg) && (b&isNeg)) return b;
    else {
        while (!((x & a) | (x & b))) {
            x = x >> 1;
        }
        if (!(x&a)) return a;
        else return b;
    }
}

int min3 (int a, int b, int c) {
    return min2(a, min2(b, c));
}

int main (int argc, char* argv[]) {
    printf("Min of 3,2,1 is: %d\n", min3(3,2,1));
    printf("Min of 2,1,4 is: %d\n", min3(2,1,4));
    printf("Min of -2,1,80 is: %d\n", min3(-2,1,80));
    printf("Min of 123,456,789 is: %d\n", min3(123,456,789));
    printf("Min of -123,-456,-789 is: %d\n", min3(-123,-456,-789));
}
```
reply permalink
Len - 12 years ago
And after posting I realize I over-engineered the problem. The poster above me points out correctly that you just need to determine if the difference of two numbers is positive or negative.
```
int min2 (int a, int b) {
    int isNeg = 0x8000;
    int diff = a - b;
    if (diff&isNeg) return a;
    else return b;
}
```
reply permalink
Anonymous - 12 years ago
def minimum(a,b,c): if bool(len(str(math.sqrt((a-b)2))) - len(str(float(a-b)))): minimum = a else: minimum = b if not bool(len(str(math.sqrt((minimum-c)2))) - len(str(float(minimum-c)))): minimum = c return minimum

reply permalink

tehMagik - 12 years ago

A simple solution without negative checks:

def MinOf3(a, b, c):
    #small % large = small
    try:
        #check c <= b
        1 / (b - (b % c) )
        try:
            #check c <= a
            1 / (a - (a % c))
            return c
        except:
            #a < c <= b
            return a
    except:
        #a = ?, b < c
        #check b < a
        try:
            1 / (a - (a % b))
            return b
        except:
            #a <= b < c
            return a

print("Smallest: %d" % MinOf3(7,8,9))

reply permalink

vick - 12 years ago

My humble solution:

public class SmallestInteger {

private static int min(int a, int b) {
    long al = a;
    long bl = b;
    long signbit = ((al - bl) >>> 63);
    return (int) (signbit * a + (1 - signbit) * b);
}

public static int smallestIntegerOf(int a, int b, int c) {
    return min(min(a, b), c);
}

public static void main(String[] args) {
    System.out.println(smallestIntegerOf(150, -2, 3));
}

}

reply permalink

Ethan - 12 years ago
According to the problem, it wouldn't be cheating to ask for user input that specifies to enter the numbers in order.

reply permalink

Adam - 12 years ago

def min3(a, b, c):
    return min2(min2(a, b), c)

def min2(a, b):
    return (a + b - abs(a - b)) // 2

reply permalink

Valetudinarian - 12 years ago
I am no programmer myself, but I have a few suggestions for those of the required knowledge who could reconcile my ideas into the requested language.

Assuming that these integers are indicated by the variables a,b, and c. Due to the author's forbidding us the use of a comparison operator, we may suffice ourselves with a solution we could pick from, using the basic arithmetic operations.

Assuming that these integers could be selected randomly, this opens the probability that one of these integers will be a zero. If all integers will undergo the exact same operation then it ought to suffice regardless the plugged value. Division by zero does not meet this requirement, thus division must be discarded.

SUBTRACTION AND THE ABSOLUTE VALUE: In addition to the zero, the integers contain negative values. To elaborate more explicitly, if we were to compare the subtraction of 'b from a' to 'c from a' if we've proposed that 'b' is a negative value while 'c' isn't, then the former returns a greater value than the second. Regardless whether the absolute value of 'b' is greater or lesser than the value of 'c' itself. Hence, how the usage of the absolute value is misleading in this context.

We cannot use any comparison notations, therefore, we are left with an equation (or set thereof) equaling a determined value. If, for any given value, passes the requirements to solve, then it is the smallest integer among the given three. Of course, the operation MUSTN'T have any division BY A VARIABLE, with an attempt to avoid subtraction. Multiplication and addition may suffice.

Again, this is a bit of an early time for me to begin cleaning my white board and actually solving this dilemma. Perhaps later on will I return to assist.

reply permalink

Calum - 12 years ago

    static int Min(int a, int b, int c)
    {
        return Min2(Min2(a, b), c);
    }

    static int Min2(int a, int b)
    {
        try
        {
            DateTime.MaxValue.AddHours(a - b);
            return a;
        }
        catch
        {
            return b;
        }
    }

reply permalink

vj - 12 years ago
Here's my two cents ```c #include <stdio.h>

int my_abs(int num) { if(num >> sizeof(int) * 8 - 1) return -num; else return num; }

int min(int a,int b, int c) { int min = a;
```
if(!(my_abs(min-b)-(min-b)))
    min = b;

if(!(my_abs(min-c)-(min-c)))
    min = c;

return min; 
```
}

int main() { printf("Min[1,2,3] = %d\n",min(1,2,3)); printf("Min[-1,-2,-3] = %d\n",min(-1,-2,-3)); printf("Min[1,-2,3] = %d\n",min(1,-2,3)); // your code goes here return 0; } ```

reply permalink

vj - 12 years ago

#include <stdio.h>
int my_abs(int num) 
{
    if(num >> sizeof(int) * 8 - 1)
        return -num;
    else 
        return num;
}

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

    if(!(my_abs(min-b)-(min-b)))
        min = b;

    if(!(my_abs(min-c)-(min-c)))
        min = c;

    return min; 
}

int main() {
    printf("Min[1,2,3] = %d\n",min(1,2,3));
    printf("Min[-1,-2,-3] = %d\n",min(-1,-2,-3));
    printf("Min[1,-2,3] = %d\n",min(1,-2,3));
    // your code goes here
    return 0;
}

reply permalink

Problem of the Day A new programming or logic puzzle every Mon-Fri

Smallest Integer

Comments:

Problem of the Day
A new programming or logic puzzle every Mon-Fri