Bit Shuffle With OR and XOR

Medium

You get two binary strings of the same length, start and goal. You may apply this operation to start any number of times: - pick two different indices i and j; - at the same time, replace start[i] with start[i] OR start[j] and start[j] with start[i] XOR start[j] (both formulas use the old values). For example, "0110" with i = 0, j = 2 becomes "1110". Return True if start can be turned into goal this way, and False otherwise.

Example 1

start="001", goal="110" → True

i = 0, j = 2: "001" → "101". Then i = 1, j = 2: "101" → "111". Finally i = 0, j = 2: 1 OR 1 = 1 and 1 XOR 1 = 0, giving "110".

Example 2

start="000", goal="010" → False

Operations on zeros only ever produce zeros: 0 OR 0 = 0 and 0 XOR 0 = 0. There is no way to create a 1.

Example 3

start="10", goal="00" → False

Once there is a 1 it cannot be destroyed: with a pair (1, x) position i keeps 1 OR x = 1, and with (0, 1) position i becomes 1.

Constraints

2 ≤ len(start) ≤ 10⁵
len(goal) == len(start)
Both strings contain only the characters 0 and 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation String

Similar problems

Recurring Gene Windows Medium Words With No Shared Letters Medium Every Shorthand of a Word Medium Fewest Address Blocks Medium Every Case Spelling Medium

Input

start="001", goal="110"

Expected

True

Run checks the first 3 tests in your browser. Submit checks all 98 tests on the server, hidden ones included.