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

Apply Bitwise Operations to Make Strings Equal

Number: 2632

Difficulty: Medium

Paid? No

Companies: Sprinklr

Problem Description

Given two 0-indexed binary strings s and target of the same length, you are allowed to perform an operation any number of times. In each operation, choose two different indices i and j, then simultaneously update s[i] to (s[i] OR s[j]) and s[j] to (s[i] XOR s[j]). The goal is to determine whether you can transform string s into target using these operations.

Key Insights

  • The allowed operation works on two bits simultaneously and has predictable outcomes:
    • (0, 0) → (0, 0)
    • (0, 1) or (1, 0) → (1, 1)
    • (1, 1) → (1, 0)
  • If target contains at least one '1', then it is mandatory for s to have at least one '1' because 1s are the only source to “spread” ones to the rest of the string.
  • If target is composed entirely of '0's, then s must also be all '0's. If s contains any '1', you cannot completely remove it.
  • The transformation essentially depends on whether s has at least one '1' when target requires at least one '1', and s equals target if target is all zero.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string, since we only need to scan s and target. Space Complexity: O(1), as we use a constant amount of extra space.

Solution

The solution involves checking two main conditions:

  1. If target has no '1's (i.e. it is all zeros), then s must also be all zeros; otherwise, it is not possible.
  2. If target contains at least one '1', then s must also contain at least one '1' to “spread” the ones throughout via the allowed operation.

We can determine the answer by simply checking for the presence of '1' in s and target. No complex simulation is required due to the properties of how the bitwise operations work.

Code Solutions

# Python solution with line-by-line comments
def make_strings_equal(s: str, target: str) -> bool:
    # Check if target has any '1'
    if "1" not in target:
        # If target is all zeros, s must also be all zeros.
        return "1" not in s
    else:
        # If target has at least one '1', s must contain a '1' to spread it.
        return "1" in s

# Example usage:
print(make_strings_equal("1010", "0110"))  # Output: True
print(make_strings_equal("11", "00"))      # Output: False
← Back to All Questions