Algorithm
Problem Name: Data Structures -
https://www.hackerrank.com/challenges/ab0/problem?isFullScreen=true
In this HackerRank in Data Structures -
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.
Code Examples
#1 Code Example with C Programming
Code -
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("%lld\n",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;
}
#2 Code Example with C++ Programming
Code -
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;
}
#3 Code Example with Java Programming
Code -
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();
}
}
#4 Code Example with Python Programming
Code -
Python Programming
#!/bin/python3
import math
import os
import random
import re
import sys
#
# Complete the 'solve' function below.
#
# The function is expected to return an INTEGER_ARRAY.
# The function accepts following parameters:
# 1. INTEGER p
# 2. STRING s
# 3. 2D_INTEGER_ARRAY queries
#
def solve(p, s, queries):
bigNumber = str(s)
count=0
result = []
for i in queries:
count=0
q=i[1]+2-i[0]
for j in range(i[0],i[1]+1):
for k in range(1,q):
if (int(bigNumber[j-1:j+k-1]))%p==0:
count+=1
q-=1
result.append(count)
return result
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
first_multiple_input = input().rstrip().split()
p = int(first_multiple_input[0])
q = int(first_multiple_input[1])
s = input()
queries = []
for _ in range(q):
queries.append(list(map(int, input().rstrip().split())))
result = solve(p, s, queries)
fptr.write('\n'.join(map(str, result)))
fptr.write('\n')
fptr.close()