Apply Bitwise Operations to Make Strings Equal - Solution & Explanation

Q: Is Apply Bitwise Operations to Make Strings Equal easy or hard?

The problem is rated Medium because the implementation is simple but the insight about bitwise invariants is not immediately obvious. Many candidates initially try to simulate operations, but the correct solution comes from recognizing that the existence of a '1' cannot be created from zero or completely removed.

Q: Apply Bitwise Operations to Make Strings Equal Python/Java solution

In Python or Java, the implementation usually checks whether '1' appears in each string using built‑in string search functions. For example, in Python you can use `'1' in s` and `'1' in target`. In Java, use `s.contains("1")`. If both results match, return true; otherwise return false.

Q: How to solve Apply Bitwise Operations to Make Strings Equal in O(n)?

Scan both strings and determine whether each contains at least one '1'. If both have a '1', you can use OR to spread that bit and XOR to flip positions to match the target. If neither string has a '1', both are already all zeros and therefore equalizable. If exactly one string contains a '1', the transformation is impossible.

Q: What is the best approach for Apply Bitwise Operations to Make Strings Equal?

The optimal approach checks whether both strings contain at least one '1'. Bitwise OR can spread a 1 across positions, and XOR can flip bits when another 1 exists. However, you cannot create the first 1 from all zeros or remove the last remaining 1. Therefore, the transformation is possible only if both strings either contain a '1' or both contain none. This runs in O(n) time and O(1) space.

Q: Is Apply Bitwise Operations to Make Strings Equal asked at Google/Amazon/Meta?

Problems involving bit manipulation and transformation invariants are common in interviews at companies like Google, Amazon, and Meta. This specific question tests reasoning about OR and XOR behavior rather than implementation complexity, which is a pattern frequently seen in technical screens.

Q: What data structure is used in Apply Bitwise Operations to Make Strings Equal?

No complex data structure is required. The solution works directly on the input strings and uses simple boolean checks to determine whether a '1' exists. The focus is on understanding bitwise operations rather than using additional storage.

Q: What is the time complexity of Apply Bitwise Operations to Make Strings Equal?

The optimal solution runs in O(n) time where n is the length of the binary strings. You only scan each string once to check whether it contains a '1'. The space complexity is O(1) because the algorithm stores only a few boolean flags.

MediumString Bit Manipulation13 min readAsked at: Sprinklr

Practice this problem

Problem Statement

You are given two 0-indexed binary strings s and target of the same length n. You can do the following operation on s any number of times:

Choose two different indices i and j where 0 <= i, j < n.
Simultaneously, replace s[i] with (s[i] OR s[j]) and s[j] with (s[i] XOR s[j]).

For example, if s = "0110", you can choose i = 0 and j = 2, then simultaneously replace s[0] with (s[0] OR s[2] = 0 OR 1 = 1), and s[2] with (s[0] XOR s[2] = 0 XOR 1 = 1), so we will have s = "1110".

Return true if you can make the string s equal to target, or false otherwise.

Example 1:

Input: s = "1010", target = "0110"
Output: true
Explanation: We can do the following operations:
- Choose i = 2 and j = 0. We have now s = "0010".
- Choose i = 2 and j = 1. We have now s = "0110".
Since we can make s equal to target, we return true.

Example 2:

Input: s = "11", target = "00"
Output: false
Explanation: It is not possible to make s equal to target with any number of operations.

Constraints:

n == s.length == target.length
2 <= n <= 10⁵
s and target consist of only the digits 0 and 1.

Approach Overview

Problem Overview: You are given two binary strings s and target. You can repeatedly choose two different indices and replace s[i] with either s[i] OR s[j] or s[i] XOR s[j]. The goal is to determine whether these operations can transform s into target.

Approach 1: Count Ones and Zeros (O(n) time, O(1) space)

Iterate through both strings and count the number of '1' characters. The key observation comes from how the allowed operations behave. OR can spread a 1 to other positions, while XOR can flip bits if another 1 exists in the string. Because of this, once a string contains at least one 1, you can propagate or flip bits to build any configuration that also contains a 1. However, if the string contains no 1, all operations keep it zero forever. The transformation is possible only when both strings either contain at least one 1 or both contain none. Counting provides a straightforward way to check this condition.

This method performs a single pass through each string, using constant memory. The counts themselves are not strictly required beyond determining whether a 1 exists, but they make the reasoning explicit and easy to verify.

Approach 2: Presence of Both Digits (O(n) time, O(1) space)

The optimal approach simplifies the previous idea even further. Instead of counting, check whether each string contains at least one '1'. The allowed operations create a useful invariant: you cannot generate the first 1 if the string starts with all zeros, and you cannot eliminate the final 1 once it exists. This means the existence of a 1 in the string never changes from zero to non‑zero or vice versa.

Compute hasOneS = s.contains('1') and hasOneT = target.contains('1'). If both values match, the transformation is possible. If one string has a 1 and the other does not, no sequence of operations can bridge that gap.

This solution uses a single linear scan and constant extra space. The reasoning relies on understanding how bitwise operations propagate bits, which makes it a good exercise when practicing bit manipulation and string processing problems.

Recommended for interviews: The presence-check approach is what most interviewers expect. It shows that you recognized the invariant created by the bitwise operations rather than simulating transformations. A counting version demonstrates the same idea but is slightly more verbose. The optimal insight—checking whether both strings share the same "contains 1" state—demonstrates strong reasoning about bitwise operations.

Approach 1: Approach 1: Count Ones and Zeros

This approach is based on the idea that, to convert the string s to the target using the described operations, you need to either transform a '0' to a '1' or ensure both strings already match with respect to the position's bits. To achieve a target, the count of '1's in both strings must match, as the operations cannot increase or decrease the total count of '1's.

This C implementation iterates through both strings counting the number of '1's. It then checks if these counts are equal for s and target. If they are, it returns true; otherwise, it returns false.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n) | Space Complexity: O(1)

Try this approach in the editor →

Approach 2: Approach 2: Presence of Both Digits

The critical observation here is that the operations allow us to swap '0' to '1' and vice versa, provided both '1' and '0' exist in the string. It is possible to make the transformation if and only if both strings have at least one '1' and at least one '0', or they are already identical.

This C solution checks if the strings are already equal. If not, it checks if the string s contains both '1' and '0'. If both exist, a transformation is still possible, otherwise it is not.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n) | Space Complexity: O(1)

Try this approach in the editor →

Approach 3: Lateral Thinking

We notice that 1 is actually a "tool" for number conversion. Therefore, as long as both strings either have 1 or neither have 1, we can make the two strings equal through operations.

The time complexity is O(n), where n is the length of the string. The space complexity is O(1).

Code

Python Java C++Go TypeScript Rust C

Python

Java

C++

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Approach 1: Count Ones and Zeros	Time Complexity: O(n) \| Space Complexity: O(1)
Approach 2: Presence of Both Digits	Time Complexity: O(n) \| Space Complexity: O(1)
Lateral Thinking	—

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Count Ones and Zeros	O(n)	O(1)	Good for explaining the reasoning step‑by‑step by explicitly counting digits in both strings.
Presence of Both Digits	O(n)	O(1)	Best practical solution. Only checks whether each string contains at least one '1'.

Video Solution

Apply Bitwise Operations to Make Strings Equal || Weekly Contest 329 || #Leetcode || C++ Solution • Code With U-DAY • 1,100 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Apply Bitwise Operations to Make Strings Equal easy or hard?

The problem is rated Medium because the implementation is simple but the insight about bitwise invariants is not immediately obvious. Many candidates initially try to simulate operations, but the correct solution comes from recognizing that the existence of a '1' cannot be created from zero or completely removed.

Apply Bitwise Operations to Make Strings Equal Python/Java solution

In Python or Java, the implementation usually checks whether '1' appears in each string using built‑in string search functions. For example, in Python you can use `'1' in s` and `'1' in target`. In Java, use `s.contains("1")`. If both results match, return true; otherwise return false.

How to solve Apply Bitwise Operations to Make Strings Equal in O(n)?

Scan both strings and determine whether each contains at least one '1'. If both have a '1', you can use OR to spread that bit and XOR to flip positions to match the target. If neither string has a '1', both are already all zeros and therefore equalizable. If exactly one string contains a '1', the transformation is impossible.

What is the best approach for Apply Bitwise Operations to Make Strings Equal?

The optimal approach checks whether both strings contain at least one '1'. Bitwise OR can spread a 1 across positions, and XOR can flip bits when another 1 exists. However, you cannot create the first 1 from all zeros or remove the last remaining 1. Therefore, the transformation is possible only if both strings either contain a '1' or both contain none. This runs in O(n) time and O(1) space.

Is Apply Bitwise Operations to Make Strings Equal asked at Google/Amazon/Meta?

Problems involving bit manipulation and transformation invariants are common in interviews at companies like Google, Amazon, and Meta. This specific question tests reasoning about OR and XOR behavior rather than implementation complexity, which is a pattern frequently seen in technical screens.

What data structure is used in Apply Bitwise Operations to Make Strings Equal?

No complex data structure is required. The solution works directly on the input strings and uses simple boolean checks to determine whether a '1' exists. The focus is on understanding bitwise operations rather than using additional storage.

What is the time complexity of Apply Bitwise Operations to Make Strings Equal?

The optimal solution runs in O(n) time where n is the length of the binary strings. You only scan each string once to check whether it contains a '1'. The space complexity is O(1) because the algorithm stores only a few boolean flags.

Ready to solve this problem?

Practice Apply Bitwise Operations to Make Strings Equal with our built-in code editor and test cases.

Practice on FleetCode

Minimum One Bit Operations to Make Integers Zero

Problem Info

DifficultyMedium

Acceptance42.6%

Approaches3

Reading time13 min

Asked at

Sprinklr

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Approach 1: Count Ones and Zeros

Code

Complexity

Approach 2: Approach 2: Presence of Both Digits

Code

Complexity

Approach 3: Lateral Thinking

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents