Given two binary strings s1 and s2. The XOR of them is X, the task is to find the number of ways to swap two-bit positions in string s1 such that XOR formed between new s1 and s2 is not same as X.
Examples:
Input: s1 = “01011”, s2 = “11001”
Output: 4
swap bits of index(1-based) (1, 4), (2, 3), (3, 4), or (3, 5) such that XOR value is changed.
Input: s1 = “011000”, s2 = “010011”
Output: 6
Approach:
- Count the number of 1’s and 0’s in s1.
- Traverse in the string s1, and check for two cases:
- 0 and 0 in s1[i] and s2[i], as replacing 0 with 1, will change the XOR value.
- 1 and 0 in s1[i] and s2[i], as replacing 1 with 0 will change the XOR value.
- For the first case, the number of ways of replacement will be the number of ones-already used 1’s.
- For the second case, the number of ways of replacement will be the number of zeros-already used 0’s.
- summation of number of ways in both the cases will be the answer.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;// Function that returns the number of// bit swaps such that xor is differentint countWays(string s1, string s2){ int c1 = 0, c0 = 0; int n = s1.length(); // traverse and count 1's and 0's for (int i = 0; i < n; i++) { if (s1[i] == '1') c1++; else c0++; } int used1 = 0, used0 = 0; int ways = 0; // traverse in the string for (int i = 0; i < n; i++) { // if both positions are 0 if (s1[i] == '0' and s2[i] == '0') { // add the number of ones as // it will change the XOR ways += c1; // subtract the number of ones already used ways -= used1; // zeros have been used used0++; } // when 1 and 0, to change XOR, we have to // replace 1 by 0 else if (s1[i] == '1' and s2[i] == '0') { // add number of 0's ways += c0; // subtract number of 0's already used ways -= used0; // count 1's used used1++; } } // return the answer return ways;}// Driver Codeint main(){ string s1 = "01011"; string s2 = "11001"; cout << countWays(s1, s2); return 0;} |
Java
// Java Program to find Number of// ways to change the XOR of two// numbers by swapping the bitsclass GFG{// Function that returns the // number of bit swaps such// that xor is differentstatic int countWays(String s1, String s2){ int c1 = 0, c0 = 0; int n = s1.length(); // traverse and count 1's and 0's for (int i = 0; i < n; i++) { if (s1.charAt(i) == '1') c1++; else c0++; } int used1 = 0, used0 = 0; int ways = 0; // traverse in the String for (int i = 0; i < n; i++) { // if both positions are 0 if (s1.charAt(i) == '0' && s2.charAt(i) == '0') { // add the number of ones as // it will change the XOR ways += c1; // subtract the number of // ones already used ways -= used1; // zeros have been used used0++; } // when 1 and 0, to change XOR, // we have to replace 1 by 0 else if (s1.charAt(i) == '1' && s2.charAt(i) == '0') { // add number of 0's ways += c0; // subtract number of // 0's already used ways -= used0; // count 1's used used1++; } } // return the answer return ways;}// Driver Codepublic static void main(String[] args){ String s1 = "01011"; String s2 = "11001"; System.out.println(countWays(s1, s2));}}// This code is contributed// by Arnab Kundu |
Python3
# Function that returns the number of# bit swaps such that xor is differentdef countWays(s1, s2): c1 = 0 c0 = 0 n = len(s1) # traverse and count 1's and 0's for i in range(0,n) : if (s1[i] == '1'): c1+=1 else: c0+=1 used1 = 0 used0 = 0 ways = 0 # traverse in the string for i in range(0,n) : # if both positions are 0 if (s1[i] == '0' and s2[i] == '0') : # add the number of ones as # it will change the XOR ways += c1 # subtract the number of ones already used ways -= used1 # zeros have been used used0+=1 # when 1 and 0, to change XOR, we have to # replace 1 by 0 elif (s1[i] == '1' and s2[i] == '0') : # add number of 0's ways += c0 # subtract number of 0's already used ways -= used0 # count 1's used used1+=1 # return the answer return ways# Driver Codeif __name__=='__main__': s1 = "01011" s2 = "11001" print(countWays(s1, s2))# This code is contributed by Smitha Dinesh Semwal |
C#
// C# Program to find Number of// ways to change the XOR of two// numbers by swapping the bitsusing System;class GFG{// Function that returns the // number of bit swaps such// that xor is differentstatic int countWays(String s1, String s2){ int c1 = 0, c0 = 0; int n = s1.Length; // traverse and count 1's and 0's for (int i = 0; i < n; i++) { if (s1[i] == '1') c1++; else c0++; } int used1 = 0, used0 = 0; int ways = 0; // traverse in the String for (int i = 0; i < n; i++) { // if both positions are 0 if (s1[i] == '0' && s2[i] == '0') { // add the number of ones as // it will change the XOR ways += c1; // subtract the number of // ones already used ways -= used1; // zeros have been used used0++; } // when 1 and 0, to change XOR, // we have to replace 1 by 0 else if (s1[i] == '1' && s2[i] == '0') { // add number of 0's ways += c0; // subtract number of // 0's already used ways -= used0; // count 1's used used1++; } } // return the answer return ways;}// Driver Codepublic static void Main(String[] args){ String s1 = "01011"; String s2 = "11001"; Console.WriteLine(countWays(s1, s2));}}// This code is contributed// by Subhadeep Gupta |
PHP
<?php// Function that returns the // number of bit swaps such // that xor is different function countWays($s1, $s2) { $c1 = 0; $c0 = 0; $n = strlen($s1); // traverse and count 1's and 0's for ($i = 0; $i < $n; $i++) { if ($s1[$i] == '1') $c1++; else $c0++; } $used1 = 0; $used0 = 0; $ways = 0; // traverse in the string for ($i = 0; $i < $n; $i++) { // if both positions are 0 if ($s1[$i] == '0' and $s2[$i] == '0') { // add the number of ones as // it will change the XOR $ways += $c1; // subtract the number of // ones already used $ways -= $used1; // zeros have been used $used0++; } // when 1 and 0, to change XOR, // we have to replace 1 by 0 else if ($s1[$i] == '1' and $s2[$i] == '0') { // add number of 0's $ways += $c0; // subtract number of 0's // already used $ways -= $used0; // count 1's used $used1++; } } // return the answer return $ways; } // Driver Code $s1 = "01011"; $s2 = "11001"; echo countWays($s1, $s2);// This code is contributed // by Shivi_Aggarwal?> |
Javascript
<script>// Function that returns the number of// bit swaps such that xor is differentfunction countWays(s1, s2){ let c1 = 0, c0 = 0; let n = s1.length; // traverse and count 1's and 0's for (let i = 0; i < n; i++) { if (s1[i] == '1') c1++; else c0++; } let used1 = 0, used0 = 0; let ways = 0; // traverse in the string for (let i = 0; i < n; i++) { // if both positions are 0 if (s1[i] == '0' && s2[i] == '0') { // add the number of ones as // it will change the XOR ways += c1; // subtract the number of ones already used ways -= used1; // zeros have been used used0++; } // when 1 and 0, to change XOR, we have to // replace 1 by 0 else if (s1[i] == '1' && s2[i] == '0') { // add number of 0's ways += c0; // subtract number of 0's already used ways -= used0; // count 1's used used1++; } } // return the answer return ways;}// Driver Code let s1 = "01011"; let s2 = "11001"; document.write(countWays(s1, s2));</script> |
Output:
4
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
