Modulo of a large Binary String | C ++ implementation of the approach ; Function to return the value of ( str % k ) ; pwrTwo [ i ] will store ( ( 2 ^ i ) % k ) ; To store the result ; If current bit is 1 ; Add the current power of 2 ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int getMod ( string str , int n , int 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 ; } int res = 0 ; int i = 0 , j = n - 1 ; while ( i < n ) { if ( str [ j ] == '1' ) { res += ( pwrTwo [ i ] ) ; res %= k ; } i ++ ; j -- ; } return res ; } int main ( ) { string str = "1101" ; int n = str . length ( ) ; int k = 45 ; cout << getMod ( str , n , k ) << endl ; }