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.

Input Format

The first line contains t, the number of test cases. The first line is followed by t lines, each line denoting a test case. Each test case will have two space-separated integers n, m which denote the number of letters in the language and the length of words in this language respectively.

HackerRank Alien Languages 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])

Alien Languages 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();
    }
}

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;
}

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("%dn", number[m]);
    }
    return 0;
}