# HackerRank Divisibility problem solution

In this HackerRank Divisibility problem solution, you are given two positive integers P and S., and also given two integers b and e to define a substring. so we need to calculate the divisibility of the given string.

## Problem solution in Java Programming.

```import java.io.*;
import java.util.*;

public class Solution {

static class Pair {
int fi;
int se;
int i;

public Pair(int fi, int se, int i) {
this.fi = fi;
this.se = se;
this.i = i;
}
}

public static void main(String[] args) throws IOException {
BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

int p = Integer.parseInt(st.nextToken());
int q = Integer.parseInt(st.nextToken());

int ah = 0;
int d = 1;
while ((p % 2) == 0) {
p /= 2;
ah++;
d *= 2;
}

int bh = 0;
while ((p % 5) == 0) {
p /= 5;
bh++;
d *= 5;
}

int c = Math.max(ah, bh);

int n = s.length;
long[] num = new long[n + 1];
for (int i = 0; i < n; i++) {
num[i + 1] = s[i] - '0';
}

int k = (int) Math.sqrt(n);
long power = 1;
Integer[] srt = new Integer[n + 2];
int[] g = new int[n + 2];
for (int i = n; i > 0; i--) {
srt[i + 1] = i + 1;
g[i] = (int) ((g[i + 1] + (power * num[i]) % p) % p);
power = (power * 10) % p;
}

long[] pow = new long[35];
pow[0] = 1;

for (int i = 1; i <= 32; i++) {
pow[i] = (pow[i - 1] * 10) % d;
}

srt[1] = 1;
Arrays.sort(srt, 1, n + 2, (a, b) -> g[a] - g[b]);

for (int i = 1, prev = -1, count = 0; i <= n + 1; i++) {
if (g[srt[i]] != prev) {
count++;
prev = g[srt[i]];
}

g[srt[i]] = count;
}

int[][] rightArr = new int[n + 2][35];
int[][] leftArr = new int[n + 1][35];
boolean[] ok = new boolean[n + 2];
for (int i = 1; i <= n; i++) {
long md = 0;
int j;

for (j = 0; (i - j) > 0 && j < c; j++) {
md = (md + (pow[j] * num[i - j]) % d) % d;
rightArr[i + 1][j + 1] = rightArr[i + 1][j];

if (md == 0 && g[i - j] == g[i + 1]) {
rightArr[i + 1][j + 1]++;
leftArr[i - j][j + 1]++;
}
}

if (j == c && md == 0) {
ok[i + 1] = true;
}
}

for (int i = 1; i <= n + 1; i++) {
for (int j = 0; i + j <= n && j < c; j++) {
leftArr[i][j + 1] += leftArr[i][j];
}
}

Pair[] query = new Pair[q + 1];
for (int i = 1; i <= q; i++) {
int begin = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
query[i] = new Pair(begin, end, i);
}

Arrays.sort(query, 1, 1 + q, (a, b) -> {
if (a.fi / k != b.fi / k) {
return a.fi - b.fi;
}
return a.se - b.se;
});

long sum = 0;
int left = n;
int right = n + 5;
int r = 0;
int l = 0;
int[] sizeLeft = new int[n + 1];
int[] sizeRight = new int[n + 1];
long[] ans = new long[q + 1];

for (int i = 1; i <= q; i++) {
int b = query[i].fi;
int e = query[i].se + 1;

if (e < right) {
r = b - c - 1;
l = b + c;
Arrays.fill(sizeRight, 0);
Arrays.fill(sizeLeft, 0);
left = b;
right = b - 1;
sum = 0;
}

for (int j = right + 1; j <= e; j++, r++) {
if (r >= left) {
sizeRight[g[r]]++;
}

if (j - left > c && ok[j]) {
sum += sizeRight[g[j]];
sizeLeft[g[j]]++;
}

sum += rightArr[j][Math.min(j - left, c)];
}

for (int j = left - 1; j >= b; j--, l--) {
if (ok[l] && l <= e) {
sizeLeft[g[l]]++;
}

sum += sizeLeft[g[j]] + leftArr[j][Math.min(c, e - j)];

if (e - c > j) {
sizeRight[g[j]]++;
}
}

for (int j = left; j < b; j++) {
if (l < e) {
l++;
sum -= sizeLeft[g[j]] + leftArr[j][Math.min(c, e - j)];

if (ok[l]) {
sizeLeft[g[l]]--;
}
} else {
sum -= leftArr[j][e - j];
}

if (l >= e) {
l = j + c + 1;
}

if (e - c > j) {
sizeRight[g[j]]--;
}
}

left = b;
right = e;
ans[query[i].i] = sum;
}

for (int i = 1; i <= q; i++) {
bw.write(ans[i] + "\n");
}

bw.close();
br.close();
}
}```

## Problem solution in C++ programming.

```#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>

#define fi first
#define se second

using namespace std;

typedef long long int Lint;
typedef pair<int, int> ii;
int N, Q, K, srt[110000], sizeLeft[110000], sizeRight[110000], A, B, C, D = 1,
R[110000][35], L[110000][35], OK[110000];
Lint num[110000], ans[110000], G[110000], P, POW[35]; //G[x]=f( x , N )
ii query[110000];
string s;

int compare(const int &a, const int &b) {
if (query[a].fi / K != query[b].fi / K) {
return query[a].fi < query[b].fi;
}

return query[a].se < query[b].se;
}

int compare2(const int &a, const int &b) {
return G[a] < G[b];
}

int main() {
cin >> P >> Q;
cin >> s;

while ((P % 2) == 0) {
P /= 2;
A++;
D *= 2;
}

while ((P % 5) == 0) {
P /= 5;
B++;
D *= 5;
}

C = max(A, B);
N = s.size();

for (int i = 0; i < N; i++) {
num[i + 1] = s[i] - '0';
}

K = sqrt(N);
Lint power = 1;

for (int i = N; i; i--) {
srt[i + 1] = i + 1;
G[i] = (G[i + 1] + (power * num[i]) % P) % P;
power = (power * 10LL) % P;
}

POW[0] = 1;

for (int i = 1; i <= 32; i++) {
POW[i] = (POW[i - 1] * 10) % D;
}

srt[1] = 1;
sort(srt + 1, srt + 2 + N, compare2);

for (int i = 1, prev = -1, count = 0; i <= N + 1; i++) {
if (G[srt[i]] != prev) {
count++, prev = G[srt[i]];
}

G[srt[i]] = count;
}

for (int i = 1; i <= N; i++) {
Lint md = 0;
int j;

for (j = 0; i - j && j < C; j++) {
md = (md + (POW[j] * num[i - j]) % D) % D;
R[i + 1][j + 1] = R[i + 1][j];

if (!md && G[i - j] == G[i + 1]) {
R[i + 1][j + 1]++, L[i - j][j + 1]++;
}
}

if (j == C && !md) {
OK[i + 1] = 1;
}
}

for (int i = 1; i <= N + 1; i++) {
for (int j = 0; i + j <= N && j < C; j++) {
L[i][j + 1] += L[i][j];
}
}

for (int i = 1, begin, end; i <= Q; i++) {
scanf(" %d %d", &begin, &end);
query[i] = ii(begin, end);
srt[i] = i;
}

sort(srt + 1, srt + 1 + Q, compare);
Lint sum = 0;
int left = N, right = N + 5, r, l;

for (int i = 1, b, e; i <= Q; i++) {
b = query[srt[i]].fi, e = query[srt[i]].se + 1;

if (e < right) {
r = b - C - 1, l = b + C;
memset(sizeRight, 0, sizeof sizeRight);
memset(sizeLeft, 0, sizeof sizeLeft);
left = b, right = b - 1;
sum = 0;
}

for (int j = right + 1; j <= e; j++, r++) {
if (r >= left) {
sizeRight[G[r]]++;
}

if (j - left > C && OK[j]) {
sum += sizeRight[G[j]], sizeLeft[G[j]]++;
}

sum += R[j][min(j - left, C)];
}

for (int j = left - 1; j >= b; j--, l--) {
if (OK[l] && l <= e) {
sizeLeft[G[l]]++;
}

sum += sizeLeft[G[j]] + L[j][min(C, e - j)];

if (e - C > j) {
sizeRight[G[j]]++;
}
}

for (int j = left; j < b; j++) {
if (l < e) {
l++;
sum -= sizeLeft[G[j]] + L[j][min(C, e - j)];

if (OK[l]) {
sizeLeft[G[l]]--;
}
} else {
sum -= L[j][e - j];
}

if (l >= e) {
l = j + C + 1;
}

if (e - C > j) {
sizeRight[G[j]]--;
}
}

left = b;
right = e;
ans[srt[i]] = sum;
}

for (int i = 1; i <= Q; i++) {
printf("%lld\n", ans[i]);
}

return 0;
}```

## Problem solution in C programming.

```#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define HASH_SIZE 123455
typedef struct _node{
int x;
int c;
struct _node *next;
} node;
void QQ(int x,int y);
void remove_left(int X);
void remove_right(int X);
void sort_a3(int*a,int*b,int*c,int size);
void merge3(int*a,int*left_a,int*right_a,int*b,
int*left_b,int*right_b,int*c,int*left_c,int*right_c,
int left_size,int right_size);
void insert(node **hash,int x);
void removee(node **hash,int x);
int count(node **hash,int x);
node *get();
void free_node(node *x);
char S[100001];
int cl,cr,a[100001],q1[100000],q2[100000],
y[100000],idx[100000],g1[100000][30],g2[100000]={0},
g3[100000][30],x;
long long ans[100000],tans;
node *hash1[HASH_SIZE]={0},*hash2[HASH_SIZE]={0},

int main(){
int P,Q,N,P1,i,j;
long long t,t1;
for(i=0;i<200000;i++)
if(i!=200000-1)
pool[i].next=&pool[i+1];
else
pool[i].next=NULL;
scanf("%d%d%s",&P,&Q,S);
N=strlen(S);
for(i=0;i<Q;i++){
scanf("%d%d",q1+i,q2+i);
q1[i]--;
q2[i]--;
}
for(i=0,x=(int)sqrt(N);i<Q;i++){
a[i]=q1[i]/x;
y[i]=q2[i];
idx[i]=i;
}
sort_a3(a,y,idx,Q);
for(x=0,P1=1;P%2==0;){
P/=2;
P1*=2;
x++;
}
for(t=0;P%5==0;){
P/=5;
P1*=5;
t++;
}
x=(x>t)?x:t;
for(i=N-1,t=1;i>=0;i--,t=t*10%P)
if(i==N-1)
a[i]=(S[i]-'0')%P;
else
a[i]=(a[i+1]+(S[i]-'0')*t)%P;
a[N]=0;
if(!x)
for(i=0;i<N;i++)
g2[i]=1;
else{
for(i=0;i<N;i++)
for(t=0,t1=1,j=0;j<x && i-j>=0;j++,t1*=10){
t=t+(S[i-j]-'0')*t1;
if(!j)
if(t%(P1*P)==0)
g1[i][j]=1;
else
g1[i][j]=0;
else
if(t%(P1*P)==0)
g1[i][j]=g1[i][j-1]+1;
else
g1[i][j]=g1[i][j-1];
}
for(i=x-1;i<N;i++){
for(t=0,j=i-x+1;j<i+1;j++)
t=t*10+S[j]-'0';
if(t%P1==0)
g2[i]=1;
}
for(i=0;i<N;i++)
for(t=0,j=0;j<x && i+j<N;j++){
t=t*10+(S[i+j]-'0');
if(!j)
if(t%(P1*P)==0)
g3[i][j]=1;
else
g3[i][j]=0;
else
if(t%(P1*P)==0)
g3[i][j]=g3[i][j-1]+1;
else
g3[i][j]=g3[i][j-1];
}
}
for(i=cl=cr=0,tans=0;i<Q;i++){
QQ(q1[idx[i]],q2[idx[i]]);
ans[idx[i]]=tans;
}
for(i=0;i<Q;i++)
printf("%lld\n",ans[i]);
return 0;
}
void QQ(int x,int y){
while(cl<x)
remove_left(cl++);
while(cl>x)
while(cr<y+1)
while(cr>y+1)
remove_right(--cr);
return;
}
if(X>=cr)
return;
if(X+x<cr){
insert(hash1,a[X]);
if(g2[X+x])
insert(hash2,a[X+x+1]);
tans+=count(hash2,a[X]);
if(x)
tans+=g3[X][x-1];
}
else
tans+=g3[X][cr-X-1];
return;
}
if(X<cl)
return;
if(X-x>=cl){
insert(hash1,a[X-x]);
if(g2[X]){
insert(hash2,a[X+1]);
tans+=count(hash1,a[X+1]);
}
if(x)
tans+=g1[X][x-1];
}
else
tans+=g1[X][X-cl];
return;
}
void remove_left(int X){
if(X>=cr)
return;
if(X+x<cr){
removee(hash1,a[X]);
tans-=count(hash2,a[X]);
if(g2[X+x])
removee(hash2,a[X+x+1]);
if(x)
tans-=g3[X][x-1];
}
else
tans-=g3[X][cr-X-1];
return;
}
void remove_right(int X){
if(X<cl)
return;
if(X-x>=cl){
if(g2[X]){
tans-=count(hash1,a[X+1]);
removee(hash2,a[X+1]);
}
if(x)
tans-=g1[X][x-1];
removee(hash1,a[X-x]);
}
else
tans-=g1[X][X-cl];
return;
}
void sort_a3(int*a,int*b,int*c,int size){
if (size < 2)
return;
int m = (size+1)/2,i;
int *left_a,*left_b,*left_c,*right_a,*right_b,*right_c;
left_a=(int*)malloc(m*sizeof(int));
right_a=(int*)malloc((size-m)*sizeof(int));
left_b=(int*)malloc(m*sizeof(int));
right_b=(int*)malloc((size-m)*sizeof(int));
left_c=(int*)malloc(m*sizeof(int));
right_c=(int*)malloc((size-m)*sizeof(int));
for(i=0;i<m;i++){
left_a[i]=a[i];
left_b[i]=b[i];
left_c[i]=c[i];
}
for(i=0;i<size-m;i++){
right_a[i]=a[i+m];
right_b[i]=b[i+m];
right_c[i]=c[i+m];
}
sort_a3(left_a,left_b,left_c,m);
sort_a3(right_a,right_b,right_c,size-m);
merge3(a,left_a,right_a,b,left_b,right_b,c,
left_c,right_c,m,size-m);
free(left_a);
free(right_a);
free(left_b);
free(right_b);
free(left_c);
free(right_c);
return;
}
void merge3(int*a,int*left_a,int*right_a,
int*b,int*left_b,int*right_b,int*c,
int*left_c,int*right_c,int left_size,
int right_size){
int i = 0, j = 0;
while (i < left_size|| j < right_size) {
if (i == left_size) {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
c[i+j] = right_c[j];
j++;
} else if (j == right_size) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
c[i+j] = left_c[i];
i++;
} else if (left_a[i] == right_a[j]) {
if(left_b[i]<=right_b[j]){
a[i+j] = left_a[i];
b[i+j] = left_b[i];
c[i+j] = left_c[i];
i++;
}
else{
a[i+j] = right_a[j];
b[i+j] = right_b[j];
c[i+j] = right_c[j];
j++;
}
} else if (left_a[i] < right_a[j]) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
c[i+j] = left_c[i];
i++;
} else {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
c[i+j] = right_c[j];
j++;
}
}
return;
}
void insert(node **hash,int x){
node *t=hash[x%HASH_SIZE];
while(t){
if(t->x==x){
t->c++;
return;
}
t=t->next;
}
t=get();
t->x=x;
t->c=1;
t->next=hash[x%HASH_SIZE];
hash[x%HASH_SIZE]=t;
return;
}
void removee(node **hash,int x){
node *t=hash[x%HASH_SIZE],*p=NULL;
while(t){
if(t->x==x){
t->c--;
return;
}
p=t;
t=t->next;
}
return;
}
int count(node **hash,int x){
node *t=hash[x%HASH_SIZE];
while(t){
if(t->x==x)
return t->c;
t=t->next;
}
return 0;
}
node *get(){
return res;
}
void free_node(node *x){
return;
}```