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.

HackerRank String Transmission 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)

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

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

    StringTokenizer st = new StringTokenizer(br.readLine());
    int t = Integer.parseInt(st.nextToken());

    for (int tItr = 0; tItr < t; tItr++) {
      st = new StringTokenizer(br.readLine());

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

      String s = br.readLine();
      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("%dn", 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("%dn",(g(N,p)+1000000007)%1000000007);
    }
    exit(0);
}