Maximum bitwise and after increment operations

impl Solution {
  pub fn maximum_and(nums: Vec<i32>, k: i32, m: i32) -> i32 {
    let n = nums.len();
    let m = m as usize;
    let k = k as i64;

    // Greedy bit-by-bit from highest to lowest.
    // Try to set bit b in the answer. If we can find m elements that can all
    // have bits [current_answer | bit_b] set with total cost <= k, keep that bit.

    // To check if a target value (with certain bits set) is achievable:
    // For each element, compute the cost to make it have all target bits set.
    // The cost to make nums[i] have all bits in `target` set:
    // We need nums[i]' >= some value that has all target bits set.
    // The minimum value with all target bits set that is >= nums[i]:
    // If nums[i] already has all target bits set, cost is 0.
    // Otherwise, we need to increment nums[i] to the next value that has all target bits.

    // For a given target (a mask), the cost for element x:
    // Find the smallest y >= x such that y & target == target.
    // Cost = y - x.

    // To find smallest y >= x with y & target == target:
    // Start with y = target. If y >= x, done.
    // Otherwise, we need to find the next value above x that has all target bits set.

    let cost_to_reach = |x: i64, target: i64| -> i64 {
      if x & target == target {
        return 0;
      }
      // Find smallest y >= x such that y & target == target
      // We process bits from high to low.
      // y must have all bits of target set, and y >= x.
      // Start with y = target. If y >= x, return y - x.
      if target >= x {
        return target - x;
      }
      // target < x but target has bits that x doesn't have.
      // We need to find the smallest y >= x with (y & target) == target.
      //
      // Strategy: look at bits from high to low.
      // For each bit position in target that is set, y must have it set.
      // For bit positions not in target, y can have any value.
      // We want the smallest such y >= x.
      //
      // This is like: find smallest y >= x where y OR target == y (i.e., target is subset of y's bits)
      // Equivalently, y = target | free_bits, minimize y subject to y >= x.

      // Simple approach: iterate from highest bit down
      // Let's just compute it directly.
      // We need all bits of target set in y. The free bits (not in target) can be anything.
      // So y = target | z where z can use any bits not in target (and also target bits are already set).
      // Actually y can have any bits set as long as target's bits are all set.
      // So y = target | extra, where extra is any non-negative integer.
      // We want smallest y = target | extra >= x.
      // Since target | extra >= target, and target < x, we need extra to supply the difference.

      // Actually, the simplest correct approach:
      // y must have all target bits set. Let free_mask = !target (bits we can freely set).
      // We want to find the smallest y >= x with y & target == target.
      // y = target | (y & free_mask). Let f = y & free_mask. Then y = target | f.
      // We need target | f >= x. Since target bits are fixed, we need to choose f
      // (using only bits in free_mask) to minimize target | f subject to target | f >= x.

      // Hmm, this is getting complicated. Let me use a different approach.
      // Just find the next value >= x with all target bits set.

      // Go bit by bit from MSB to LSB:
      let mut y = x;
      // Set all target bits in y. If a target bit is not set in y, we need to set it,
      // which might cause carries.
      // Process from lowest bit to highest to handle carries.

      // Alternative simpler approach:
      // The values with all target bits set form an arithmetic-like sequence.
      // Actually they don't form an arithmetic sequence in general.

      // Let's try: set all target bits in x. If any target bit was 0 in x, setting it
      // increases x. But we also need to clear bits below to minimize.
      //
      // Correct algorithm:
      // For each bit in target from low to high that is NOT set in current y, set it.
      // But this may create a value less than x if we also need to clear higher bits.
      //
      // Actually let me just use a simple formula:
      // missing = target & !x  (bits in target not in x)
      // If missing == 0, cost is 0 (handled above).
      // Otherwise, find the highest missing bit, say bit b.
      // Set bit b in x, clear all bits below b in x, then set all target bits.
      // This gives a value >= x with all target bits set.

      // Let me think again more carefully...
      // We want smallest y >= x, y & target == target.
      //
      // Approach: greedily build y from MSB to LSB.
      // We track whether y is already > x in the prefix (then we can set remaining bits minimally)
      // or y == x in the prefix (then we're constrained).

      // This is essentially a digit-DP but we can do it greedily.

      // Simple and correct: just add the missing bits one at a time from lowest.
      // When we set a missing bit, it might already be satisfied due to carry from addition.

      // Actually, the simplest correct O(30) approach:
      // Compute y = x, then for each bit in target not set in y (from low to high),
      // round y up to the next multiple that has that bit set.
      // But this is tricky with interactions.

      // Let me just do: try y = (x | target). If y >= x and y & target == target, done.
      // x | target always has target bits set, and x | target >= x. So y = x | target works!

      // Wait... x | target >= x always, and (x | target) & target == target always.
      // So the answer is just (x | target) - x = (x | target) - x.
      // But is x | target the SMALLEST such y? Not necessarily.
      // For example, x = 0b101, target = 0b010. x | target = 0b111 = 7.
      // But y = 0b010 = 2 < 5 = x, so that doesn't work. y = 0b110 = 6 > 5 and has bit 1 set.
      // Cost would be 6 - 5 = 1. x | target = 7 - 5 = 2. So x | target is not optimal.

      // Hmm, so we need a better approach. Let me think...
      // For x = 5 = 0b101, target = 0b010:
      // We need y >= 5 with bit 1 set. Candidates: 6(110), 10(1010), 14(1110)...
      // Smallest is 6. Cost = 1.
      // x | target = 7. Cost = 2. Not optimal.

      // OK so x | target is an upper bound but not always optimal.
      // The correct approach: find smallest y >= x with (y & target) == target.

      // Greedy from MSB: we have 30 bits. Let's say bits 29..0.
      // At each bit position, we decide the bit of y.
      // If the bit is required by target, it must be 1.
      // Otherwise, we try to match x's bit (to stay equal), or if we're already above, set 0.

      // If at some point the required bit forces y above x, we're free to minimize the rest.
      // If at some point the required bit forces y below x (required 1 but x has 1 and we
      // need to set 0... no, required bits are always 1, so if target bit is 1, y bit is 1.
      // If target bit is 0, y bit is free.

      // Cases at each bit position (processing from MSB to LSB):
      // State: "equal" (y prefix == x prefix so far) or "greater" (y prefix > x prefix)
      //
      // If "greater": set y bit to target bit (forced 1 if target, else 0 to minimize)
      // If "equal":
      //   If target bit = 1:
      //     If x bit = 1: y bit = 1, stay "equal"
      //     If x bit = 0: y bit = 1, become "greater"
      //   If target bit = 0 (free):
      //     Try y bit = x bit first (stay "equal")
      //     (If later we find it's impossible to satisfy, backtrack to y bit = 1 -> "greater")

      // But we might not need backtracking if we're careful. Actually for this problem,
      // since free bits can be anything and required bits are 1:
      // When "equal" and target bit = 0, if x bit = 0, set y = 0, stay equal.
      //   If x bit = 1, set y = 1, stay equal.
      // When "equal" and target bit = 1, if x bit = 1, set y = 1, stay equal.
      //   If x bit = 0, set y = 1, now "greater", minimize rest.

      // The issue is: when equal and target = 0 and x = 1, we set y = 1 to stay equal.
      // But what if later a target bit is 1 and x bit is 0? Then y becomes greater at that point.
      // That's fine - y is still valid.

      // Wait, the problematic case is: equal, target bit = 0, x bit = 1. We set y = 1.
      // But later: equal, target bit = 1, x bit = 1. We set y = 1, still equal.
      // And then: equal, target bit = 0, x bit = 1, and the remaining bits can't satisfy.
      // Hmm no, free bits can always be set to match x, so "equal" path always works until
      // a forced bit differs from x. If forced bit = 1 and x bit = 0, we go to "greater"
      // (good, y > x). If forced bit = 1 and x bit = 1, stay equal. If free bit, match x.
      //
      // So actually the "equal" path never fails - we either stay equal or become greater.
      // We never need y bit < x bit because required bits are 1 (>= any x bit of 0, = x bit of 1).
      // And free bits match x.

      // So the greedy algorithm works without backtracking!

      let mut y = 0i64;
      let mut state = 0; // 0 = equal, 1 = greater
      for b in (0..31).rev() {
        let target_bit = (target >> b) & 1;
        let x_bit = (x >> b) & 1;
        if state == 1 {
          // Already greater, minimize: set to target_bit
          y |= target_bit << b;
        } else {
          // Equal so far
          if target_bit == 1 {
            y |= 1 << b;
            if x_bit == 0 {
              state = 1; // now greater
            }
          } else {
            // Free bit, match x to stay equal
            y |= x_bit << b;
          }
        }
      }
      y - x
    };

    let mut answer = 0i32;

    // Try to build answer from highest bit to lowest
    // At each step, try to set the current bit. Check if we can achieve (answer | bit)
    // with at most m elements and cost <= k.

    for bit in (0..31).rev() {
      let candidate = answer | (1 << bit);
      let target = candidate as i64;

      // Compute cost for each element to reach target, pick m smallest
      let mut costs: Vec<i64> = nums.iter().map(|&x| cost_to_reach(x as i64, target)).collect();
      costs.sort_unstable();

      let total: i64 = costs.iter().take(m).sum();
      if total <= k {
        answer = candidate;
      }
    }

    answer
  }
}