# HackerRank String Transmission problem solution

In this HackerRank String Transmission problem solution, Bob has received a binary string of length N transmitted by Alice. He knows that due to errors in transmission, up to K bits might have been corrupted (and hence flipped). However, he also knows that the string Alice had intended to transmit was not periodic. A string is not periodic if it cannot be represented as a smaller string concatenated some number of times. For example, "0001", "0110" are not periodic while "00000", "010101" are periodic strings. Now he wonders how many possible strings could Alice have transmitted.

## Problem solution in Python.

```T = int(input())
M = 1000000007

from math import factorial, sqrt

def nck(n, k):
res = 0

for i in range(k+1):
res += factorial(n)//(factorial(i)*factorial(n-i))
return res

def divisors(n):
d1 = [1]
d2 = []
for i in range(2, int(sqrt(n)) + 1):
if n % i == 0:
d1.append(i)
if i*i != n:
d2.append(n//i)
d1.extend(d2[::-1])
return d1

for _ in range(T):

N, K = [int(x) for x in input().split()]
S = input()
if N == 1:
print(N+K)
continue

total = nck(N, K)
div = divisors(N)
dp = [[0]*(N+K+1) for i in range(len(div))]
is_periodic = False

for i, d in enumerate(div):
dp[i][0] = 1
for offset in range(d):
zeros = 0

for j in range(offset, N, d):
if S[j] == "0":
zeros += 1
ones = N//d - zeros

prev = list(dp[i])
dp[i][:] = [0]*(N+K+1)

for k in range(K+1):
if prev[k]:
dp[i][k + zeros] += prev[k]
dp[i][k + ones] += prev[k]

if dp[i][0]:
is_periodic = True

for i2 in range(i):
d2 = div[i2]
if d % d2 == 0:
for k in range(K+1):
dp[i][k] -= dp[i2][k]

for k in range(1, K+1):
total -= dp[i][k]

print((total-is_periodic) % M)```

## Problem solution in Java.

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

public class Solution {

static final int N = 1001;
static final int MOD = 1_000_000_007;

static int[] getPrimes() {
int[] pr = new int[168];
int[] mu = new int[N];
boolean[] sieved = new boolean[N];
int np = 0;
mu[1] = 1;
for (int i = 2; i < N; i++) {
if (!sieved[i]) {
pr[np++] = i;
mu[i] = -1;
}
for (int j = 0; j < np && i * pr[j] < N; j++) {
sieved[i * pr[j]] = true;
if (i % pr[j] == 0) {
mu[i * pr[j]] = 0;
break;
}
mu[i * pr[j]] = -mu[i];
}
}
return mu;
}

static int[][] getBinomials() {
int[][] binom = new int[N+1][N+1];
for (int i = 0; i <= N; i++) {
binom[i][0] = binom[i][i] = 1;
for (int j = 1; j < i; j++) {
binom[i][j] = (binom[i - 1][j - 1] + binom[i - 1][j]) % MOD;
}
}
return binom;
}

static int stringTransmission(int k, char[] a, int n, int[] mu, int[][] binom) {
int[] dp = new int[k+1];
int ans = 0;
for (int i = 2; i <= n; i++) {
if ((n % i) == 0 && mu[i] != 0) {
int m = n / i;
Arrays.fill(dp, 0);
dp[0] = 1;
for (int j = 0; j < m; j++) {
int x = 0;
for (int g = j; g < n; g += m) {
x += a[g] == '1' ? 1 : 0;
}
int y = i - x;
for (int g = k + 1; --g >= 0;) {
dp[g] = ((g < x ? 0 : dp[g - x]) + (g < y ? 0 : dp[g - y])) % MOD;
}
}
long sum = 0;
for (int j = 0; j <= k; j++) {
sum = (sum + dp[j]) % MOD;
}
ans = (int) ((ans + sum * mu[i]) % MOD);
}
}

for (int i = 0; i <= k; i++) {
ans = (ans + binom[n][i]) % MOD;
}
return (ans + MOD) % MOD;
}

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

int[] mu = getPrimes();
int[][] binom = getBinomials();

int t = Integer.parseInt(st.nextToken());

for (int tItr = 0; tItr < t; tItr++) {

int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());

int result = stringTransmission(k, s.toCharArray(), n, mu, binom);

bw.write(String.valueOf(result));
bw.newLine();
}

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

## Problem solution in C++.

```#include <cstdio>
#include <iostream>
#include <cstring>

using namespace std ;

#define add(reg, val) {reg += val ; if (reg >= modul) reg -= modul ; }

int n, k, bin [1001] [1001], modul = 1000000007 ;

int main() {
memset(bin, 0, sizeof(bin)) ;
bin [0] [0] = 1 ;
for (int i = 1 ; i < 1001 ; i ++) {
bin [i] [0] = 1 ;
for (int j = 1 ; j < 1001 ; j ++) {
add(bin [i] [j], bin [i - 1] [j - 1] + bin [i - 1] [j]) ;
}
}

int numTests, dp [1001] [2], c [1001] [2], period [1001] ;
scanf("%d", &numTests) ;
char s [1001] ;
for (int test = 0 ; test < numTests ; test ++) {
scanf("%d%d%s", &n, &k, s) ;
int len = strlen(s), total = 0 ;
for (int kk = 0 ; kk <= k ; kk ++) add(total, bin [n] [kk]) ;
for (int d = 1 ; d < len ; d ++) if (len % d == 0) {
for (int i = 0 ; i < d ; i ++) for (int ch = 0 ; ch <= 1 ; ch ++) c [i] [ch] = 0 ;
int j = 0 ;
for (int i = 0 ; i < len ; i ++) {
c [j] [s [i] - '0'] ++ ;
j ++ ;
if (j >= d) j -= d ;
}
memset(dp, 0, sizeof(dp)) ;
dp [0] [0] = 1 ;
int cur = 0, ncur, rep = n / d ;
for (int i = 0 ; i < d ; i ++) {
ncur = cur ^ 1 ;
for (int j = 0 ; j <= k ; j ++) dp [j] [ncur] = 0 ;
for (int j = 0 ; j <= k ; j ++) if (dp [j] [cur]) {
for (int ch = 0 ; ch <= 1 ; ch ++)
if (j + c [i] [ch] <= k) add(dp [j + c [i] [ch]] [ncur], dp [j] [cur]) ;
}
cur = ncur ;
}
period [d] = 0 ;
for (int i = 0 ; i <= k ; i ++) add(period [d], dp [i] [cur]) ;
for (int dd = 1 ; dd < d ; dd ++) if (d % dd == 0) add(period [d], modul - period [dd]) ;
add(total, modul - period [d]) ;
}

printf("%d\n", total) ;
}
return 0 ;
}```

## Problem solution in C.

```#include <stdlib.h>
#include <stdio.h>
int N,K;
int F[1000][1000],S[1000];
char s[1001];
int f(int x, int i, int j) {
if(j>K) return 0;
if(i==x) return 1;
if(F[i][j]==-1) F[i][j] = (f(x,i+1,j+S[i])+f(x,i+1,j+N/x-S[i]))%1000000007;;
return F[i][j];
}
int g(int x, int *p) {
if((*p)!=0) return (g(x,p+1)-g(x/(*p),p+1))%1000000007;
int i,j;
for(i=0; i<x; i++) for(j=0; j<=K; j++) F[i][j] = -1;
for(i=0; i<x; i++) {
S[i] = 0;
for(j=i; j<N; j+=x) S[i]+= (s[j]=='1')?1:0;
}
return f(x,0,0);
}
int main() {
int i,j,k,T;
int ps[170],l[500],p[5];
for(i=0;i<500;i++) l[i] = 1;
ps[0] = 2;
for(i=3,k=1;i<1000;i+=2) if(l[i/2]) {
ps[k++] = i;
for(j=i*i/2;j<500;j+=i) l[j] = 0;
}
scanf("%d",&T);
for(;T>0;T--) {
scanf("%d %d %[01]",&N,&K,s);
for(i=0,j=0; i<k; i++) if(N%ps[i]==0) p[j++] = ps[i];
p[j] = 0;
printf("%d\n",(g(N,p)+1000000007)%1000000007);
}
exit(0);
}```