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.

HackerRank Alien Languages problem solution


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}