|
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 {
public static int modulo(String s, int m) {
int ans = 0;
int power = 1;
for (int i = s.length() - 1; i >= 0; i--) {
if (s.charAt(i) == '1') {
ans += power;
ans %= m;
}
power *= 2;
power %= m;
}
return ans;
}
public static void main(String[] args) {
String s = "101";
int m = 2;
int result = modulo(s, m);
System.out.println(result);
}
}
|
Python3
def modulo(s, m):
ans = 0
power = 1
for i in range(len(s) - 1, -1, -1):
if s[i] == '1':
ans += power
ans %= m
power *= 2
power %= m
return ans
def main():
s = "101"
m = 2
result = modulo(s, m)
print(result)
if __name__ == "__main__":
main()
|
C#
using System;
public class GFG
{
public static int Modulo(string s, int m)
{
int ans = 0;
int power = 1;
for (int i = s.Length - 1; i >= 0; i--)
{
if (s[i] == '1')
{
ans += power;
ans %= m;
}
power *= 2;
power %= m;
}
return ans;
}
public static void Main(string[] args)
{
string s = "101";
int m = 2;
int result = Modulo(s, m);
Console.WriteLine(result);
}
}
|
Javascript
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);
|
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.
|
