We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Flips to Make a OR b Equal to c

Number: 1441

Difficulty: Medium

Paid? No

Companies: Microsoft

Problem Description

Given three positive integers a, b, and c, determine the minimum number of bit flips required on a and b so that the bitwise OR (a OR b) equals c. A single flip changes a 0 to a 1 or a 1 to a 0 in the binary representation.

Key Insights

  • For each bit position, extract the corresponding bits from a, b, and c.
  • If the target bit in c is 0, both bits in a and b must be 0; any 1's must be flipped.
  • If the target bit in c is 1, at least one of a or b must be 1; if both are 0, one flip is required.
  • Iterate through all 32 bits (since a, b, and c can be as large as 10^9) to compute the total flips.

Space and Time Complexity

Time Complexity: O(1) – We process a constant 32 bits regardless of the input values. Space Complexity: O(1) – Only a fixed amount of extra space is used.

Solution

The solution iterates over each bit position (0 through 31) and examines the bits of a, b, and c:

  1. Extract the bit at the current position for a, b, and c.
  2. If the bit in c is 0, then any 1s in a or b at that position are extra and need to be flipped.
  3. If the bit in c is 1, then if both a and b have 0 at that bit position, one flip is needed to make it 1.
  4. Sum the flips required for each bit position.

This bit-by-bit approach ensures that we only flip the necessary bits and correctly account for cases where both bits contribute to the discrepancy.

Code Solutions

def minFlips(a: int, b: int, c: int) -> int:
    flips = 0
    # Process each bit position from 0 to 31
    for i in range(32):
        # Extract the i-th bit of a, b, and c
        bit_a = (a >> i) & 1  # Get i-th bit of a
        bit_b = (b >> i) & 1  # Get i-th bit of b
        bit_c = (c >> i) & 1  # Get i-th bit of c
        
        # If c's bit is 0, then both a and b must have 0 at i-th bit
        if bit_c == 0:
            if bit_a == 1:
                flips += 1  # Flip bit from 1 to 0 in a
            if bit_b == 1:
                flips += 1  # Flip bit from 1 to 0 in b
        else:
            # If c's bit is 1, at least one among a or b must be 1
            if bit_a == 0 and bit_b == 0:
                flips += 1  # Flip one of the bits from 0 to 1
        
    return flips

# Example usage:
print(minFlips(2, 6, 5))  # Output: 3
← Back to All Questions