# 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 {
BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

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

for (int i = 0; i < t; i++) {
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}