Modulo of a large Binary String
Given a large binary string str and an integer K, the task is to find the value of str % K.
Examples:
Input: str = “1101”, K = 45
Output: 13
decimal(1101) % 45 = 13 % 45 = 13Input: str = “11010101”, K = 112
Output: 101
decimal(11010101) % 112 = 213 % 112 = 101
Approach: It is known that (str % K) where str is a binary string can be written as ((str[n – 1] * 20) + (str[n – 2] * 21) + … + (str[0] * 2n – 1)) % K which in turn can be written as (((str[n – 1] * 20) % K) + ((str[n – 2] * 21) % K) + … + ((str[0] * 2n – 1)) % K) % K. This can be used to find the required answer without actually converting the given binary string to its decimal equivalent.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the value of (str % k) int getMod(string str, int n, int k) { // pwrTwo[i] will store ((2^i) % k) int pwrTwo[n]; pwrTwo[0] = 1 % k; for ( int i = 1; i < n; i++) { pwrTwo[i] = pwrTwo[i - 1] * (2 % k); pwrTwo[i] %= k; } // To store the result int res = 0; int i = 0, j = n - 1; while (i < n) { // If current bit is 1 if (str[j] == '1' ) { // Add the current power of 2 res += (pwrTwo[i]); res %= k; } i++; j--; } return res; } // Driver code int main() { string str = "1101" ; int n = str.length(); int k = 45; cout << getMod(str, n, k) << endl; } // This code is contributed by ashutosh450 |
Java
// Java implementation of the approach import java.util.*; class GFG { // Function to return the value of (str % k) static int getMod(String str, int n, int k) { // pwrTwo[i] will store ((2^i) % k) int pwrTwo[] = new int [n]; pwrTwo[ 0 ] = 1 % k; for ( int i = 1 ; i < n; i++) { pwrTwo[i] = pwrTwo[i - 1 ] * ( 2 % k); pwrTwo[i] %= k; } // To store the result int res = 0 ; int i = 0 , j = n - 1 ; while (i < n) { // If current bit is 1 if (str.charAt(j) == '1' ) { // Add the current power of 2 res += (pwrTwo[i]); res %= k; } i++; j--; } return res; } // Driver code public static void main(String[] args) { String str = "1101" ; int n = str.length(); int k = 45 ; System.out.print(getMod(str, n, k)); } } |
Python3
# Python3 implementation of the approach # Function to return the value of (str % k) def getMod(_str, n, k) : # pwrTwo[i] will store ((2^i) % k) pwrTwo = [ 0 ] * n pwrTwo[ 0 ] = 1 % k for i in range ( 1 , n): pwrTwo[i] = pwrTwo[i - 1 ] * ( 2 % k) pwrTwo[i] % = k # To store the result res = 0 i = 0 j = n - 1 while (i < n) : # If current bit is 1 if (_str[j] = = '1' ) : # Add the current power of 2 res + = (pwrTwo[i]) res % = k i + = 1 j - = 1 return res # Driver code _str = "1101" n = len (_str) k = 45 print (getMod(_str, n, k)) # This code is contributed by # divyamohan123 |
C#
// C# implementation of the above approach using System; class GFG { // Function to return the value of (str % k) static int getMod( string str, int n, int k) { int i; // pwrTwo[i] will store ((2^i) % k) int []pwrTwo = new int [n]; pwrTwo[0] = 1 % k; for (i = 1; i < n; i++) { pwrTwo[i] = pwrTwo[i - 1] * (2 % k); pwrTwo[i] %= k; } // To store the result int res = 0; i = 0; int j = n - 1; while (i < n) { // If current bit is 1 if (str[j] == '1' ) { // Add the current power of 2 res += (pwrTwo[i]); res %= k; } i++; j--; } return res; } // Driver code public static void Main() { string str = "1101" ; int n = str.Length; int k = 45; Console.Write(getMod(str, n, k)); } } // This code is contributed by AnkitRai01 |
Javascript
<script> // Javascript implementation of the approach // Function to return the value of (str % k) function getMod(str, n, k) { // pwrTwo[i] will store ((2^i) % k) var pwrTwo = Array(n); pwrTwo[0] = 1 % k; for ( var i = 1; i < n; i++) { pwrTwo[i] = pwrTwo[i - 1] * (2 % k); pwrTwo[i] %= k; } // To store the result var res = 0; var i = 0, j = n - 1; while (i < n) { // If current bit is 1 if (str[j] == '1' ) { // Add the current power of 2 res += (pwrTwo[i]); res %= k; } i++; j--; } return res; } // Driver code var str = "1101" ; var n = str.length; var k = 45; document.write( getMod(str, n, k)); </script> |
13
Time Complexity: O(n)
Auxiliary Space: O(n)
Contact Us