How to write a LessThan method without using the operator

Question

How would you recursively write a method that checks if a number is less than the other without using the '<' operator?

1. You can only use the plus, minus, times, and equals operators.
2. It must be recursive
3. x and y will always be 0 or greater
4. Should return boolean
5. If needed, you can make other methods but they must follow rules above.

Cove I've got so far:

public static boolean isLessThan(int x, int y) { 
    if(x == y - 1) return true;
    if(x == y + 1) return false; 
    if(x == y) return false; 

    return isLessThan((x), (y-1)) || isLessThan((x-1), y);
}

Answer 1

Because you have made a good-faith attempt by writing your own code, and because I see this is a kind of puzzle, I'm offering you below code which has only a single recursive call rather than having two recursive calls like in your code.

I think this is as simple as it gets while satisfying the constraints.

What it does: it counts down both numbers to zero, and checks which one reaches zero first. If both reach zero at the same time, the result should be false, but simply checking whether y is zero already includes that check.

public static boolean isLessThan(int x, int y) {
    if (y == 0) {
        return false;
    }
    if (x == 0) {
        return true;
    }

    return isLessThan(x - 1, y - 1);
}

@Andreas' answer is more efficient than the above. My aim initially was for a short, clean answer. I've tried to create a shorter bitshift approach. Although harder to grasp than the counting example, it has a better complexity and it has an equal amount of lines as the above code (I'm not counting that constant as I could include it inside the code at the expense of readability).

Note that this code shifts left rather than right and - it checks the most significant bit first.

public static final int HIGH_BIT = 1 << 31;

public static boolean isLessThan(int x, int y) {
    if (x == y) {
        return false;
    }
    if ((x & HIGH_BIT) != (y & HIGH_BIT)) {
        return (y & HIGH_BIT) == HIGH_BIT;
    }
    return isLessThan(x << 1, y << 1);
}

Note: if != is disallowed, you can change the second if statement to:

if (((x ^ y) & HIGH_BIT) == HIGH_BIT)

Also note that the complexity is really O(1) as, although the algorithm is theoretically O(log n), Java ints are 32 bits so the upper bounds is O(32) which is the same as O(1).

Answer 2

You could do it like the answer to this question:
Bitwise operations equivalent of greater than operator

However that doesn't honor rule 2: It must be recursive.

According to comment, rule 1 should be:

1. You can only use plus, minus, multiply, equals, and bitwise operators.

With the use of the right-shift operator, we can get a solution in O(log n) time, unlike answer by Erwin Bolwidt, which is O(n) time, and likely to cause StackOverflowError.

public static boolean isLessThan(int x, int y) {
    return compare(x, y) == -1;
}

private static int compare(int x, int y) {
    if (x == y)
        return 0;  // x == y
    if (x == 0)
        return -1; // x < y
    if (y == 0)
        return 1;  // x > y

    // Compare higher bits. If different, then that is result
    int cmp = compare(x >> 1, y >> 1);
    if (cmp != 0)
        return cmp;

    // Only bit 0 differs, so two choices:
    //   x0 == 1 && y0 == 0 -> return 1
    //   x0 == 0 && y0 == 1 -> return -1
    return (x & 1) - (y & 1);
}

If != is not allowed, code can be changed to:

// same code up to and including recursive call
if (cmp == 0)
    return (x & 1) - (y & 1);
return cmp;