Quick Overview

Given a binary string x and a limit on how many ones another string y may contain, construct the binary string y of the same length that maximizes x XOR y. It tests reasoning about bit significance, optimization under a limit on set bits, and producing a unique, correctly formatted string answer.

Choose a bit string with at most maxSet ones to maximize its XOR with x

Company: J.P. Morgan

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given a binary string `x` of length `bits`, written with the most significant bit first, and an integer `maxSet`. Construct a binary string `y` of the same length that contains at most `maxSet` characters equal to `'1'` and makes the value of `x XOR y`, read as an unsigned binary number, as large as possible. Return `y`. ### Function Signature ```python def max_xor_partner(x: str, bits: int, maxSet: int) -> str: ``` ### Rules - `x` and `y` are read most significant bit first; leading zeros are part of the string. - `x XOR y` is computed bit by bit: a bit of the result is `1` exactly when the corresponding bits of `x` and `y` differ. - `y` must have exactly `bits` characters, each `'0'` or `'1'`, and at most `maxSet` of them may be `'1'`. Using fewer than `maxSet` ones is allowed. - Exactly one string `y` reaches the maximum value of `x XOR y`, so the answer is unique. ### Constraints - `1 <= bits <= 10^5` - `len(x) == bits`, and every character of `x` is `'0'` or `'1'`. - `0 <= maxSet <= bits` ### Examples **Example 1** ```text Input: x = "0101", bits = 4, maxSet = 1 Output: "1000" ``` `x XOR y = "1101"`, which is 13. No other `y` with at most one `'1'` gives a larger value. **Example 2** ```text Input: x = "1100", bits = 4, maxSet = 3 Output: "0011" ``` `x XOR y = "1111"`, which is 15, the largest possible 4-bit value. This `y` uses only two of the three allowed ones. **Example 3** ```text Input: x = "111", bits = 3, maxSet = 2 Output: "000" ``` `x XOR y = "111"`, already the largest possible 3-bit value, so `y` needs no ones.

Overview: Given a binary string x and a limit on how many ones another string y may contain, construct the binary string y of the same length that maximizes x XOR y. It tests reasoning about bit significance, optimization under a limit on set bits, and producing a unique, correctly formatted string answer.

Read the full J.P. Morgan Software Engineer interview experience this question came from

You are given a binary string `x` of length `bits`, written with the most significant bit first, and an integer `maxSet`. Construct a binary string `y` of the same length that contains at most `maxSet` characters equal to `'1'` and makes the value of `x XOR y`, read as an unsigned binary number, as large as possible. Return `y`. ### Rules - `x` and `y` are read most significant bit first; leading zeros are part of the string. - `x XOR y` is computed bit by bit: a bit of the result is `1` exactly when the corresponding bits of `x` and `y` differ. - `y` must have exactly `bits` characters, each `'0'` or `'1'`, and at most `maxSet` of them may be `'1'`. Using fewer than `maxSet` ones is allowed. - Exactly one string `y` reaches the maximum value of `x XOR y`, so the answer is unique. ### Constraints - `1 <= bits <= 10^5` - `len(x) == bits`, and every character of `x` is `'0'` or `'1'`. - `0 <= maxSet <= bits` `bits` and `maxSet` fit in a 32-bit signed integer. The numbers that `x`, `y` and `x XOR y` represent can have up to 10^5 bits, far beyond 2^63 - 1, so they are passed and returned only as strings. ### Examples **Example 1** ```text Input: x = "0101", bits = 4, maxSet = 1 Output: "1000" ``` `x XOR y = "1101"`, which is 13. No other `y` with at most one `'1'` gives a larger value. **Example 2** ```text Input: x = "1100", bits = 4, maxSet = 3 Output: "0011" ``` `x XOR y = "1111"`, which is 15, the largest possible 4-bit value. This `y` uses only two of the three allowed ones.

Constraints

  • 1 <= bits <= 10^5
  • len(x) == bits, and every character of x is '0' or '1'
  • 0 <= maxSet <= bits

Examples

Input: ('0', 1, 0)

Expected Output: '0'

Explanation: Minimum size with no ones allowed: y must be '0'.

Input: ('0', 1, 1)

Expected Output: '1'

Explanation: Minimum size: flipping the single zero makes x XOR y = 1.

Hints

  1. Two binary strings of the same length compare as unsigned numbers at the first position where they differ, so a more significant bit outweighs all less significant bits combined.
  2. Compare what a '1' in y does to the result bit when the matching bit of x is '1' and when it is '0'.
  3. When the allowance cannot cover every useful position, ask which positions deserve it first.

Community answers

Answer by shahdharmil3103

we can traverse from the left of the given string x and if it 0 we use one of the maxset 1 to set the ith char in the y string to get the maximum xor value and repeatly we can do untill we are left with maxset 1s to set in the y

Loading coding console...

Show the approach

Approach

Algorithm: scan x from the most significant bit (index 0) to the least significant, keeping a counter of ones still available, initially maxSet. At an index where x has '0' and the counter is positive, write '1' into y and decrement the counter; at every other index write '0'. Invariant: after each prefix, y has spent its ones on exactly the most significant zeros of x seen so far, up to maxSet of them, and has never placed a '1' where x has '1'. Correctness: two binary strings of the same length compare as unsigned numbers at their first differing index, so one more significant result bit outweighs all less significant bits combined. A '1' in y where x has '1' clears that result bit, so it can only lower the value while using allowance. A '1' where x has '0' sets that result bit. If some y skipped a more significant zero of x while spending a one on a less significant position, moving that one up to the skipped zero would make the result larger at the first changed index, so y would not be maximal. Therefore the unique optimum places min(maxSet, number of zeros in x) ones on the most significant zeros of x and nothing else, which is exactly what the scan produces. Edge cases: maxSet = 0 returns all zeros; an all-ones x returns all zeros even when maxSet = bits; when maxSet is at least the number of zeros, y is the bitwise complement of x and uses fewer ones than allowed. The output always has exactly bits characters, and the numbers are never converted, so strings of 10^5 bits are handled directly.

Time complexity:
O(bits)
Space complexity:
O(bits)