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 {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    StringTokenizer st = new StringTokenizer(br.readLine());
    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);

    char[] s = br.readLine().toCharArray();
    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++) {
      st = new StringTokenizer(br.readLine());
      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("%lldn", 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 add_left(int X);
void add_right(int X);
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},
pool[200000],*pool_head;

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;
pool_head=pool;
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("%lldn",ans[i]);
return 0;
}
void QQ(int x,int y){
while(cl<x)
remove_left(cl++);
while(cl>x)
add_left(--cl);
while(cr<y+1)
add_right(cr++);
while(cr>y+1)
remove_right(--cr);
return;
}
void add_left(int X){
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;
}
void add_right(int X){
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(){
node *res=pool_head;
if(pool_head)
pool_head=pool_head->next;
return res;
}
void free_node(node *x){
x->next=pool_head;
pool_head=x;
return;
}