Problem

Compute the integer average of two integers a and b using only integer-type operations. The integer average is defined as the greatest integer less than or equal to the exact average (i.e., floor((a+b)/2.0)).

Assumptions and constraints:

  • Use only integer variables (no floating-point, no casts to wider types unless listed as a fallback).
  • Inputs fit in the language’s signed 32-bit int range (if you choose a 64-bit fallback, state it explicitly).

Examples

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

Input: a = 4, b = 5
Output: 4

Input: a = 4, b = 6
Output: 5

Input: a = -4, b = -6
Output: -5

Input: a = 4, b = -5
Output: -1

Input: a = -4, b = -5
Output: -5

Notes

  • The naive expression (a + b) / 2 is conceptually correct but can fail in two ways:
    • overflow when a and b are large with same sign (e.g., INT_MAX and INT_MAX).
    • language-specific integer division and remainder semantics for negative numbers — be explicit about floor semantics.

Solution

We show three methods. Method 2 (bitwise) is compact and avoids overflow on two’s-complement machines with arithmetic right shift (works in Java, Kotlin, Python; on C/C++/Rust it depends on implementation but commonly behaves correctly). Method 3 is a safe fallback using 64-bit arithmetic when available.

Method 1 — Naive (a + b) / 2 (exhibits overflow)

Intuition

Directly compute the average using integer arithmetic. This matches floor for positive/negative examples when the sum fits in the integer range.

Approach

  1. Compute sum = a + b and return sum / 2.

Edge cases: overflow when a and b have same sign and large magnitude.

Code

1
2
3
4

class Solution {
 public:
  static int avg_naive(int a, int b) { return (a + b) / 2; }
};
1

func AvgNaive(a, b int) int { return (a + b) / 2 }
1
2
3

class Solution {
  public static int avgNaive(int a, int b) { return (a + b) / 2; }
}
1

object Solution { fun avgNaive(a: Int, b: Int): Int = (a + b) / 2 }
1
2
3

class Solution:
    def avg_naive(self, a: int, b: int) -> int:
        return (a + b) // 2
1
2

pub struct Solution;
impl Solution { pub fn avg_naive(a: i32, b: i32) -> i32 { (a + b) / 2 } }

Complexity

  • ⏰ Time complexity: O(1).
  • 🧺 Space complexity: O(1).

Method 2 — Bitwise safe formula (recommended for two’s-complement systems)

Intuition

Use bitwise identities to compute the average without forming a + b directly. The identity:

avg = (a & b) + ((a ^ b) >> 1)

derives from decomposing a + b = (a & b) * 2 + (a ^ b); dividing by two and using bit operations yields the formula. It avoids overflow because it never forms a + b as a single value.

This formula requires an arithmetic right shift (>>) that preserves the sign bit for negative numbers (Java and Kotlin guarantee arithmetic shift; C/C++/Rust typically perform arithmetic shift on two’s-complement platforms — note the language caveat below).

Approach

  1. Compute x = a & b and y = a ^ b.
  2. Return x + (y >> 1).

Properties:

  • No intermediate a + b is computed, so same-sign overflow is avoided.
  • Produces floor((a+b)/2) for two’s-complement arithmetic with arithmetic right shift.

Code

1
2
3
4
5
6

class Solution {
 public:
  static int avg_bitwise(int a, int b) {
    return (a & b) + ((a ^ b) >> 1);
  }
};
1
2
3

func AvgBitwise(a, b int) int {
  return (a & b) + ((a ^ b) >> 1)
}
1
2
3
4
5

class Solution {
  public static int avgBitwise(int a, int b) {
    return (a & b) + ((a ^ b) >> 1);
  }
}
1
2
3

object Solution {
  fun avgBitwise(a: Int, b: Int): Int = (a and b) + ((a xor b) shr 1)
}
1
2
3

class Solution:
    def avg_bitwise(self, a: int, b: int) -> int:
        return (a & b) + ((a ^ b) >> 1)
1
2
3
4

pub struct Solution;
impl Solution {
  pub fn avg_bitwise(a: i32, b: i32) -> i32 { (a & b) + ((a ^ b) >> 1) }
}

Complexity

  • ⏰ Time complexity: O(1).
  • 🧺 Space complexity: O(1).

Caveats: This method relies on two’s-complement representation and an arithmetic right shift. Java/Kotlin/Python/Rust (on typical targets) and mainstream C/C++ compilers on two’s-complement machines make this safe. If you target a platform/language where signed right shift is logical (fills with zero) or two’s-complement is not used, prefer the 64-bit fallback below.

Method 3 — 64-bit (wider-type) fallback (portable and simple)

Intuition

If a wider integer type (e.g., 64-bit long/long long) is permitted, promote operands to the wider type, compute the sum safely, then divide and cast back. This is the simplest portable solution if the constraint “use only 32-bit ints” is relaxed.

Approach

  1. Cast a and b to 64-bit L.
  2. Compute ans = (L(a) + L(b)) / 2.
  3. Cast result back to 32-bit int if desired.

Code

1
2
3
4
5
6
7

class Solution {
 public:
  static int avg_64(int a, int b) {
    long long s = (long long)a + (long long)b;
    return (int)(s / 2);
  }
};
1

func Avg64(a, b int64) int64 { return (a + b) / 2 }
1
2
3
4
5
6

class Solution {
  public static int avg64(int a, int b) {
    long s = (long) a + (long) b;
    return (int) (s / 2L);
  }
}
1

object Solution { fun avg64(a: Int, b: Int): Int = ((a.toLong() + b.toLong()) / 2).toInt() }
1
2
3
4

class Solution:
    def avg_64(self, a: int, b: int) -> int:
        s = int(a) + int(b)
        return s // 2
1
2
3
4

pub struct Solution;
impl Solution {
  pub fn avg_64(a: i32, b: i32) -> i32 { (((a as i64) + (b as i64)) / 2) as i32 }
}

Complexity

  • ⏰ Time complexity: O(1).
  • 🧺 Space complexity: O(1).