Problem

Find the maximum of two numbers without using any if-else statements, branching, or direct comparisons.

Examples

Example 1

1
2
3

Input: a = 5, b = 3
Output: 5
Explanation: The maximum of 5 and 3 is 5, determined without using conditionals.

Example 2

1
2
3

Input: a = -2, b = 7
Output: 7
Explanation: The maximum of -2 and 7 is 7, handling negative numbers correctly.

Example 3

1
2
3

Input: a = 10, b = 10
Output: 10
Explanation: When both numbers are equal, either can be returned as the maximum.

Example 4

1
2
3

Input: a = -5, b = -3
Output: -3
Explanation: The maximum of -5 and -3 is -3, correctly handling negative numbers.

Similar Problems

Number of 1 Bits Counting Bits Sum of Two Integers

Solution

Method 1 – Bit Manipulation with Sign Extraction

Intuition

We can determine the maximum without conditionals by using bit manipulation to extract the sign of the difference between two numbers. The key insight is that if a - b is positive, then a is greater; otherwise, b is greater. We can extract the sign bit and use it as a selector to choose the correct number.

Approach

  1. Calculate the difference diff = a - b.
  2. Extract the sign bit of the difference by right-shifting by 31 bits (for 32-bit integers).
  3. Use the sign bit as a selector: if sign is 0 (positive diff), choose a; if sign is 1 (negative diff), choose b.
  4. Apply the formula: max = a * (1 - sign) + b * sign where sign is 0 or 1.
  5. Handle potential overflow by using a more robust sign extraction method.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    int findMax(int a, int b) {
        int diff = a - b;
        int sign = (diff >> 31) & 1;
        return a * (1 - sign) + b * sign;
    }
    
    // More robust version handling overflow
    int findMaxRobust(int a, int b) {
        long long diff = (long long)a - (long long)b;
        int sign = (diff >> 63) & 1;
        return a * (1 - sign) + b * sign;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func findMax(a, b int) int {
    diff := a - b
    sign := (diff >> 31) & 1
    return a*(1-sign) + b*sign
}

// More robust version handling overflow
func findMaxRobust(a, b int) int {
    diff := int64(a) - int64(b)
    sign := int((diff >> 63) & 1)
    return a*(1-sign) + b*sign
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public int findMax(int a, int b) {
        int diff = a - b;
        int sign = (diff >>> 31) & 1;
        return a * (1 - sign) + b * sign;
    }
    
    // More robust version handling overflow
    public int findMaxRobust(int a, int b) {
        long diff = (long)a - (long)b;
        int sign = (int)((diff >>> 63) & 1);
        return a * (1 - sign) + b * sign;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def find_max(self, a: int, b: int) -> int:
        diff = a - b
        # Python handles arbitrary precision, but we simulate 32-bit behavior
        sign = (diff >> 31) & 1 if diff < 0 else 0
        return a * (1 - sign) + b * sign
    
    def find_max_robust(self, a: int, b: int) -> int:
        diff = a - b
        sign = 1 if diff < 0 else 0
        return a * (1 - sign) + b * sign

Complexity

  • ⏰ Time complexity: O(1), constant time operations for bit manipulation and arithmetic.
  • 🧺 Space complexity: O(1), only using a constant amount of extra space.

Method 2 – Mathematical Formula with Absolute Value

Intuition

We can use the mathematical property that max(a, b) = (a + b + |a - b|) / 2. This formula works because when a > b, |a - b| = a - b, so we get (a + b + a - b) / 2 = a. When b > a, |a - b| = b - a, so we get (a + b + b - a) / 2 = b.

Approach

  1. Calculate the sum sum = a + b.
  2. Calculate the absolute difference abs_diff = |a - b|.
  3. Implement absolute value without conditionals using bit manipulation.
  4. Return (sum + abs_diff) / 2.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    int findMax(int a, int b) {
        int sum = a + b;
        int diff = a - b;
        int abs_diff = (diff + (diff >> 31)) ^ (diff >> 31);
        return (sum + abs_diff) >> 1;
    }
    
    // Alternative using multiplication to avoid potential overflow
    int findMaxSafe(int a, int b) {
        long long sum = (long long)a + b;
        long long diff = (long long)a - b;
        long long abs_diff = diff < 0 ? -diff : diff;
        return (int)((sum + abs_diff) >> 1);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

func findMax(a, b int) int {
    sum := a + b
    diff := a - b
    absDiff := (diff + (diff >> 31)) ^ (diff >> 31)
    return (sum + absDiff) >> 1
}

// Alternative using int64 to avoid overflow
func findMaxSafe(a, b int) int {
    sum := int64(a) + int64(b)
    diff := int64(a) - int64(b)
    var absDiff int64
    if diff < 0 {
        absDiff = -diff
    } else {
        absDiff = diff
    }
    return int((sum + absDiff) >> 1)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public int findMax(int a, int b) {
        int sum = a + b;
        int diff = a - b;
        int absDiff = (diff + (diff >> 31)) ^ (diff >> 31);
        return (sum + absDiff) >> 1;
    }
    
    // Alternative using long to avoid overflow
    public int findMaxSafe(int a, int b) {
        long sum = (long)a + b;
        long diff = (long)a - b;
        long absDiff = diff < 0 ? -diff : diff;
        return (int)((sum + absDiff) >> 1);
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def find_max(self, a: int, b: int) -> int:
        sum_val = a + b
        diff = a - b
        abs_diff = (diff + (diff >> 31)) ^ (diff >> 31) if diff < 0 else diff
        return (sum_val + abs_diff) >> 1
    
    def find_max_simple(self, a: int, b: int) -> int:
        return (a + b + abs(a - b)) // 2

Complexity

  • ⏰ Time complexity: O(1), constant time operations for arithmetic and bit manipulation.
  • 🧺 Space complexity: O(1), only using a constant amount of extra space.

Method 3 – Boolean Logic with Arithmetic

Intuition

We can convert the comparison result into a boolean value (0 or 1) and use it as a multiplier. The trick is to use the fact that (a >= b) can be represented as !(a < b), and we can determine a < b by checking if a - b is negative.

Approach

  1. Calculate diff = a - b.
  2. Convert the sign of diff to a boolean flag.
  3. Use the flag to select between a and b using arithmetic operations.
  4. Apply the formula based on the boolean flag.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    int findMax(int a, int b) {
        // Check if a >= b without direct comparison
        int diff = a - b;
        int is_a_greater = 1 - ((diff >> 31) & 1);
        return a * is_a_greater + b * (1 - is_a_greater);
    }
    
    // Using XOR for selection
    int findMaxXor(int a, int b) {
        int diff = a - b;
        int mask = diff >> 31; // -1 if a < b, 0 if a >= b
        return a ^ ((a ^ b) & mask);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func findMax(a, b int) int {
    diff := a - b
    isAGreater := 1 - ((diff >> 31) & 1)
    return a*isAGreater + b*(1-isAGreater)
}

// Using XOR for selection
func findMaxXor(a, b int) int {
    diff := a - b
    mask := diff >> 31 // -1 if a < b, 0 if a >= b
    return a ^ ((a ^ b) & mask)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public int findMax(int a, int b) {
        int diff = a - b;
        int isAGreater = 1 - ((diff >>> 31) & 1);
        return a * isAGreater + b * (1 - isAGreater);
    }
    
    // Using XOR for selection
    public int findMaxXor(int a, int b) {
        int diff = a - b;
        int mask = diff >> 31; // -1 if a < b, 0 if a >= b
        return a ^ ((a ^ b) & mask);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def find_max(self, a: int, b: int) -> int:
        diff = a - b
        is_a_greater = 1 - (1 if diff < 0 else 0)
        return a * is_a_greater + b * (1 - is_a_greater)
    
    def find_max_xor(self, a: int, b: int) -> int:
        diff = a - b
        mask = -1 if diff < 0 else 0
        return a ^ ((a ^ b) & mask)

Complexity

  • ⏰ Time complexity: O(1), constant time operations using bit manipulation and arithmetic.
  • 🧺 Space complexity: O(1), only using a constant amount of extra space.