Sub | C ++ program to answer multiple queries of divisibility by 3 in substrings of a number ; Array to store the sum of digits ; Utility function to evaluate a character 's integer value ; This function receives the string representation of the number and precomputes the sum array ; This function receives l and r representing the indices and prints the required output ; Driver function to check the program
#include <iostream> NEW_LINE using namespace std ; int sum [ 1000005 ] ; int toInt ( char x ) { return int ( x ) - '0' ; } void prepareSum ( string s ) { sum [ 0 ] = 0 ; for ( int i = 0 ; i < s . length ( ) ; i ++ ) sum [ i + 1 ] = sum [ i ] + toInt ( s [ i ] ) ; } void query ( int l , int r ) { if ( ( sum [ r + 1 ] - sum [ l ] ) % 3 == 0 ) cout << " Divisible ▁ by ▁ 3 STRNEWLINE " ; else cout << " Not ▁ divisible ▁ by ▁ 3 STRNEWLINE " ; } int main ( ) { string n = "12468236544" ; prepareSum ( n ) ; query ( 0 , 1 ) ; query ( 1 , 2 ) ; query ( 3 , 6 ) ; query ( 0 , 10 ) ; return 0 ; }