Partition a number into two divisible parts | C ++ program to check if a string can be splitted into two strings such that one is divisible by ' a ' and other is divisible by ' b ' . ; Finds if it is possible to partition str into two parts such that first part is divisible by a and second part is divisible by b . ; Create an array of size len + 1 and initialize it with 0. Store remainders from left to right when divided by ' a ' ; Compute remainders from right to left when divided by ' b ' ; Find a point that can partition a number ; If split is not possible at this point ; We can split at i if one of the following two is true . a ) All characters after str [ i ] are 0 b ) String after str [ i ] is divisible by b , i . e . , str [ i + 1. . n - 1 ] is divisible by b . ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void findDivision ( string & str , int a , int b ) { int len = str . length ( ) ; vector < int > lr ( len + 1 , 0 ) ; lr [ 0 ] = ( str [ 0 ] - '0' ) % a ; for ( int i = 1 ; i < len ; i ++ ) lr [ i ] = ( ( lr [ i - 1 ] * 10 ) % a + ( str [ i ] - '0' ) ) % a ; vector < int > rl ( len + 1 , 0 ) ; rl [ len - 1 ] = ( str [ len - 1 ] - '0' ) % b ; int power10 = 10 ; for ( int i = len - 2 ; i >= 0 ; i -- ) { rl [ i ] = ( rl [ i + 1 ] + ( str [ i ] - '0' ) * power10 ) % b ; power10 = ( power10 * 10 ) % b ; } for ( int i = 0 ; i < len - 1 ; i ++ ) { if ( lr [ i ] != 0 ) continue ; if ( rl [ i + 1 ] == 0 ) { cout << " YES STRNEWLINE " ; for ( int k = 0 ; k <= i ; k ++ ) cout << str [ k ] ; cout << " , ▁ " ; for ( int k = i + 1 ; k < len ; k ++ ) cout << str [ k ] ; return ; } } cout << " NO STRNEWLINE " ; } int main ( ) { string str = "123" ; int a = 12 , b = 3 ; findDivision ( str , a , b ) ; return 0 ; }