Solving Binary String Modulo Problem
Given a string “s” and an integer “m” your objective is to calculate the remainder “r” when the decimal value of binary string “s” is divided by “m“.
Examples:
Input: s = “101”, m = 2
Output: 1
Explanation: If we have a string “(101)” its decimal equivalent is “(5)”. Therefore if we compute 5 mod 2 the result will be 1.Input: s = “1000”, m = 4
Output: 0
Explanation: If we have a string “(1000)” and m = 4 then r can be calculated as k mod m, which, in this case’s 8 mod 4. The final result will be 0.
Approach: To solve the problem
The idea is to calculate the value of each corresponding set bit and use it right away without storing it in an array, as we know the value of every higher set bit is 2x of the previous set bit so we can simply use a variable power and at every bit we multiply power with 2 to get the value of the current ith bit (value of 2i).
Steps for Implementing the above Approach:
- Initialize the answer with 0, and power with 1.
- Now run a loop over the binary string from the back side of the string(i.e. from the least significant bit of binary string).
- Check if the current bit is set or not then add the power(2i => which is stored in the power variable) into the answer and take its modulo with m.
- Now multiply power with 2 to get the next set bit value and also take it modulo with m so that it can’t overflow the integer limit.
- Return the answer.
Below is the implementation of the above idea:
C++
#include <iostream> using namespace std; int modulo(string s, int m) { int ans = 0; int power = 1; for ( int i = s.size() - 1; i >= 0; i--) { if (s[i] == '1' ) { ans += power; ans %= m; } power *= 2; power %= m; } return ans; } int main() { string s = "101" ; int m = 2; int result = modulo(s, m); cout << result << endl; return 0; } |
Java
public class Main { // Function to calculate modulo value public static int modulo(String s, int m) { int ans = 0 ; int power = 1 ; // Loop through the string in reverse order for ( int i = s.length() - 1 ; i >= 0 ; i--) { // Check if the current character is '1' if (s.charAt(i) == '1' ) { ans += power; ans %= m; } power *= 2 ; power %= m; } return ans; } // Driver code public static void main(String[] args) { String s = "101" ; int m = 2 ; int result = modulo(s, m); System.out.println(result); } } // This code is contributed by shivamgupta310570 |
Python3
def modulo(s, m): ans = 0 power = 1 # Loop through the string in reverse order for i in range ( len (s) - 1 , - 1 , - 1 ): # Check if the current digit is '1' if s[i] = = '1' : ans + = power ans % = m power * = 2 power % = m return ans # Driver code def main(): s = "101" m = 2 result = modulo(s, m) print (result) if __name__ = = "__main__" : main() |
C#
using System; public class GFG { // Function to calculate modulo value public static int Modulo( string s, int m) { int ans = 0; int power = 1; // Loop through the string in reverse order for ( int i = s.Length - 1; i >= 0; i--) { // Check if the current character is '1' if (s[i] == '1' ) { ans += power; ans %= m; } power *= 2; power %= m; } return ans; } // Driver code public static void Main( string [] args) { string s = "101" ; int m = 2; int result = Modulo(s, m); Console.WriteLine(result); } } |
Javascript
// JavaScript Implementation function modulo(s, m) { let ans = 0; let power = 1; for (let i = s.length - 1; i >= 0; i--) { if (s[i] === '1' ) { ans += power; ans %= m; } power *= 2; power %= m; } return ans; } let s = "101" ; let m = 2; let result = modulo(s, m); console.log(result); // This code is contributed by Sakshi |
1
Time Complexity:- O(N), As we are only using a single loop over the size of binary string.
Auxiliary Space:- O(1), As we are not using any extra space.
Contact Us