HackerRank Alien Languages problem solution

In this HackerRank Alien Languages, problem-solution we have given a number f languages and all have contained thousands of characters, and all the words in a language have the same number of characters in them. and we need to know how many different words exist in this language.

Problem solution in Python.

mod = 10**8 + 7

for cas in range(int(input())):
    n, m = map(int, input().strip().split())
    v = [2*i > n for i in range(n+1)]
    for i in range(n-1,-1,-1):
        v[i] += v[i + 1]
    c = []
    while v[1]:
        c.append(v[1])
        for i in range(1,n//2+1):
            v[i] = v[2*i]
        for i in range(n//2+1,n+1):
            v[i] = 0
        for i in range(n-1,-1,-1):
            v[i] = (v[i] + v[i + 1]) % mod

    f = [1] + [0]*(len(c)-1)
    for k in range(1,m+1):
        f = [sum(F * C for F, C in zip(f, c)) % mod] + f[:-1]

    print(f[0])

{"mode":"full","isActive":false}

Problem solution in Java.

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

public class Solution {

    static final long MOD = 100_000_007;

    static int alienLanguages(int n, int m) {
      int[][] t = new int[n + 1][20];
      int nb = n / 2;

      for (int i = n; i > nb; i--) {
        t[i][0] = 1;
      }
        
      int[] words = new int[m + 1];
      int[] mult = new int[20];

      for (int j = n, k = 0; j > 0; j /= 2, k++) {
        long d = 0;

        for (int i = n; i > 0; i--) {
          d = (d + t[i][k]) % MOD;
          t[i / 2][k + 1] = (int) d;
        }

        for (int i = n; i > 0; i--) {
          mult[k] = (int)((mult[k] + t[i][k]) % MOD);
        }
      }

      words[0] = 1;

      for (int i = 1; i <= m; i++) {
        long d = words[i - 1];
        for (int j = 0; mult[j] > 0 && i + j <= m; j++) {
          words[i + j] = (int)((words[i + j] + (d * mult[j]) % MOD) % MOD);
        }
      }
      return words[m];
    }

    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 t = Integer.parseInt(st.nextToken());

        for (int i = 0; i < t; i++) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());

            int result = alienLanguages(n, m);

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

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

{"mode":"full","isActive":false}

Problem solution in C++.

#include <iostream>
#include <cstring>

using namespace std;

#define MOD 100000007
#define MAX_M 500000
#define MAX_N 100000
#define MAX_L 20

int getPossibleWords(int n, int m) {
    static int words[MAX_M + 1];
    static int mult[MAX_L];
    static int t[MAX_N + 1][MAX_L];

    int i, j, k, nb = n / 2;
    long long d;

    memset(words, 0, sizeof(words));
    memset(mult, 0, sizeof(mult));
    memset(t, 0, sizeof(t));

    for (i = n; i > nb; i--)
        t[i][0] = 1;
    for (j = n, k = 0; j > 0; j /= 2, k++) {
        d = 0;
        for (i = n; i > 0; i--) {
            d = (d + t[i][k]) % MOD;
            t[i / 2][k + 1] = d;
        }

        for (i = n; i > 0; i--)
            mult[k] = (mult[k] + t[i][k]) % MOD;
    }

    words[0] = 1;
    for (i = 1; i <= m; i++) {
        d = words[i - 1];
        for (j = 0; mult[j] && i + j <= m; j++)
            words[i + j] = (words[i + j] + (d * mult[j]) % MOD) % MOD;
    }

    return words[m];
}

int main() {
    int t, n, m;

    cin >> t;
    for (int i = 0; i < t; i++) {
        cin >> n >> m;
        cout << getPossibleWords(n, m) << endl;
    }

    return 0;
}

{"mode":"full","isActive":false}

Problem solution in C.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int dp[2][100001];
long long material[17];
int number[500001];

int reduce(long long value) {
    while(value < 0)
        value += 100000007;
    return value % 100000007;
}

int main() {
    int t, n, m, middle, i, j, sum, index = 0, first, second, max_length;
    long long result;
    scanf("%d", &t);
    for (; t > 0; --t) {
        scanf("%d %d", &n, &m);
        memset(dp, 0, sizeof(dp));
        memset(material, 0, sizeof(material));

        middle = n / 2;

        for (i = middle + 1; i <= n; ++i) {
            dp[index][i] = 1;
        }

        for (i = 2; i <= m + 1; ++i) {
            index = 1 - index;
            if (i == 2) {
                sum = n - middle;
            } else {
                sum = 0;
                for (j = 1; j <= middle; ++j) {
                    if (dp[1 - index][j] == 0) {
                        break;
                    }
                    sum += dp[1 - index][j];
                    sum = reduce(sum);
                }
            }
            if (sum == 0) {
                break;
            }
            material[i - 1] = sum;

            for (j = 1; j <= middle; ++j) {
                first = (j << 1) - 1;
                second = first - 1;
                sum -= dp[1 - index][first] + dp[1 - index][second];
                sum = reduce(sum);
                dp[index][j] = sum;
            }
            for (j = middle + 1; j <= n; ++j) {
                dp[index][j] = 0;
            }
        }
        max_length = i - 2;
        number[0] = 1;
        for (i = 1; i <= m; ++i) {
            result = 0;
            for (j = 1; j <= max_length && j <= i; ++j) {
                result += material[j] * number[i - j];
                result = reduce(result);
            }
            number[i] = result;
        }
        printf("%d\n", number[m]);
    }
    return 0;
}

{"mode":"full","isActive":false}