Given two binary strings A and B of length N and M (up to 105). The task is to repeat the below process and find the answer.
Initialize ans = 0
while (B > 0)
ans += A & B (bitwise AND)
B = B / 2
print ans
Note: Answer can be very large so print Answer % 1000000007.
Examples:
Input: A = "1001", B = "10101" Output: 11 1001 & 10101 = 1, ans = 1, B = 1010 1001 & 1010 = 8, ans = 9, B = 101 1001 & 101 = 1, ans = 10, B = 10 1001 & 10 = 0, ans = 10, B = 1 1001 & 1 = 1, ans = 11, B = 0 Input: A = "1010", B = "1101" Output: 12
Approach: Since only B is getting affected in all the iterations and dividing a binary number by 2 means right shifting it by 1 bit, it can be observed that a bit in A will only be affected by the set bits in B which are on the left i.e. more significant than the current bit (including the current bit). For example, A = “1001” and B = “10101”, the least significant bit in A will only be affected by the set bits in B i.e. 3 bits in total and the most significant bit in A will only be affected by a single set bit in B i.e. the most significant bit in B as all the other set bits will not affect it in any iteration of the loop while performing bitwise AND, so the final result will be 20 * 3 + 23 * 1 = 3 + 8 = 11.
Below is the implementation of the above approach.
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define ll long long#define mod (int)(1e9 + 7)// Function to return the required resultll BitOperations(string a, int n, string b, int m){ // Reverse the strings reverse(a.begin(), a.end()); reverse(b.begin(), b.end()); // Count the number of set bits in b int c = 0; for (int i = 0; i < m; i++) if (b[i] == '1') c++; // To store the powers of 2 ll power[n]; power[0] = 1; // power[i] = pow(2, i) % mod for (int i = 1; i < n; i++) power[i] = (power[i - 1] * 2) % mod; // To store the final answer ll ans = 0; for (int i = 0; i < n; i++) { if (a[i] == '1') { // Add power[i] to the ans after // multiplying it with the number // of set bits in b ans += c * power[i]; if (ans >= mod) ans %= mod; } // Divide by 2 means right shift b>>1 // if b has 1 at right most side than // number of set bits will get decreased if (b[i] == '1') c--; // If no more set bits in b i.e. b = 0 if (c == 0) break; } // Return the required answer return ans;}// Driver codeint main(){ string a = "1001", b = "10101"; int n = a.length(), m = b.length(); cout << BitOperations(a, n, b, m); return 0;} |
Java
// Java implementation of the approachclass GFG{ static int mod = (int)(1e9 + 7);// Function to return the required resultstatic int BitOperations(String a, int n, String b, int m){ // Reverse the strings char[] ch1 = a.toCharArray(); reverse( ch1 ); a = new String( ch1 ); char[] ch2 = b.toCharArray(); reverse( ch2 ); b = new String( ch2 ); // Count the number of set bits in b int c = 0; for (int i = 0; i < m; i++) if (b.charAt(i) == '1') c++; // To store the powers of 2 int[] power = new int[n]; power[0] = 1; // power[i] = pow(2, i) % mod for (int i = 1; i < n; i++) power[i] = (power[i - 1] * 2) % mod; // To store the final answer int ans = 0; for (int i = 0; i < n; i++) { if (a.charAt(i) == '1') { // Add power[i] to the ans after // multiplying it with the number // of set bits in b ans += c * power[i]; if (ans >= mod) ans %= mod; } // Divide by 2 means right shift b>>1 // if b has 1 at right most side than // number of set bits will get decreased if (b.charAt(i) == '1') c--; // If no more set bits in b i.e. b = 0 if (c == 0) break; } // Return the required answer return ans;}static void reverse(char a[]) { int i, k,n=a.length; char t; for (i = 0; i < n / 2; i++) { t = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = t; } }// Driver codepublic static void main(String[] args){ String a = "1001", b = "10101"; int n = a.length(), m = b.length(); System.out.println(BitOperations(a, n, b, m));}}// This code contributed by Rajput-Ji |
Python3
# Python 3 implementation of the approachmod = 1000000007# Function to return the required resultdef BitOperations(a, n, b, m): # Reverse the strings a = a[::-1] b = b[::-1] # Count the number of set # bits in b c = 0 for i in range(m): if (b[i] == '1'): c += 1 # To store the powers of 2 power = [None] * n power[0] = 1 # power[i] = pow(2, i) % mod for i in range(1, n): power[i] = (power[i - 1] * 2) % mod # To store the final answer ans = 0 for i in range(0, n): if (a[i] == '1'): # Add power[i] to the ans after # multiplying it with the number # of set bits in b ans += c * power[i] if (ans >= mod): ans %= mod # Divide by 2 means right shift b>>1 # if b has 1 at right most side than # number of set bits will get decreased if (b[i] == '1'): c -= 1 # If no more set bits in b i.e. b = 0 if (c == 0): break # Return the required answer return ans# Driver codeif __name__ == '__main__': a = "1001" b = "10101" n = len(a) m = len(b) print(BitOperations(a, n, b, m))# This code is contributed by# Surendra_Gangwar |
C#
// C# implementation of the approachusing System;using System.Collections;class GFG{ static int mod = (int)(1e9 + 7);// Function to return the required resultstatic int BitOperations(string a, int n, string b, int m){ // Reverse the strings char[] ch1 = a.ToCharArray(); Array.Reverse( ch1 ); a = new string( ch1 ); char[] ch2 = b.ToCharArray(); Array.Reverse( ch2 ); b = new string( ch2 ); // Count the number of set bits in b int c = 0; for (int i = 0; i < m; i++) if (b[i] == '1') c++; // To store the powers of 2 int[] power = new int[n]; power[0] = 1; // power[i] = pow(2, i) % mod for (int i = 1; i < n; i++) power[i] = (power[i - 1] * 2) % mod; // To store the final answer int ans = 0; for (int i = 0; i < n; i++) { if (a[i] == '1') { // Add power[i] to the ans after // multiplying it with the number // of set bits in b ans += c * power[i]; if (ans >= mod) ans %= mod; } // Divide by 2 means right shift b>>1 // if b has 1 at right most side than // number of set bits will get decreased if (b[i] == '1') c--; // If no more set bits in b i.e. b = 0 if (c == 0) break; } // Return the required answer return ans;}// Driver codestatic void Main(){ string a = "1001", b = "10101"; int n = a.Length, m = b.Length; Console.WriteLine(BitOperations(a, n, b, m));}}// This code is contributed by mits |
PHP
<?php// PHP implementation of the approach $GLOBALS['mod'] = (1e9 + 7);// Function to return the required result function BitOperations($a, $n, $b, $m) { // Reverse the strings $a = strrev($a); $b = strrev($b); // Count the number of set bits in b $c = 0; for ($i = 0; $i < $m; $i++) if ($b[$i] == '1') $c++; # To store the powers of 2 $power = array() ; $power[0] = 1; // power[i] = pow(2, i) % mod for ($i = 1; $i < $n; $i++) $power[$i] = ($power[$i - 1] * 2) % $GLOBALS['mod']; // To store the final answer $ans = 0; for ($i = 0; $i < $n; $i++) { if ($a[$i] == '1') { // Add power[i] to the ans after // multiplying it with the number // of set bits in b $ans += $c * $power[$i]; if ($ans >= $GLOBALS['mod']) $ans %= $GLOBALS['mod']; } // Divide by 2 means right shift b>>1 // if b has 1 at right most side than // number of set bits will get decreased if ($b[$i] == '1') $c--; // If no more set bits in b i.e. b = 0 if ($c == 0) break; } // Return the required answer return $ans; } // Driver code $a = "1001";$b = "10101"; $n = strlen($a);$m = strlen($b); echo BitOperations($a, $n, $b, $m); // This code is contributed by Ryuga?> |
Javascript
<script> // JavaScript implementation of the approach let mod = (1e9 + 7); // Function to return the required result function BitOperations(a, n, b, m) { // Reverse the strings let ch1 = a.split(''); ch1.reverse(); a = ch1.join(""); let ch2 = b.split(''); ch2.reverse(); b = ch2.join(""); // Count the number of set bits in b let c = 0; for (let i = 0; i < m; i++) if (b[i] == '1') c++; // To store the powers of 2 let power = new Array(n); power[0] = 1; // power[i] = pow(2, i) % mod for (let i = 1; i < n; i++) power[i] = (power[i - 1] * 2) % mod; // To store the final answer let ans = 0; for (let i = 0; i < n; i++) { if (a[i] == '1') { // Add power[i] to the ans after // multiplying it with the number // of set bits in b ans += c * power[i]; if (ans >= mod) ans %= mod; } // Divide by 2 means right shift b>>1 // if b has 1 at right most side than // number of set bits will get decreased if (b[i] == '1') c--; // If no more set bits in b i.e. b = 0 if (c == 0) break; } // Return the required answer return ans; } let a = "1001", b = "10101"; let n = a.length, m = b.length; document.write(BitOperations(a, n, b, m)); </script> |
Output:
11
Time Complexity: O(m + n)
Auxiliary Space: O(n)
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!
