Skip to content
  • Home
  • Contact Us
  • About Us
  • Privacy Policy
  • DMCA
  • Linkedin
  • Pinterest
  • Facebook
thecscience

TheCScience

TheCScience is a blog that publishes daily tutorials and guides on engineering subjects and everything that related to computer science and technology

  • Home
  • Human values
  • Microprocessor
  • Digital communication
  • Linux
  • outsystems guide
  • Toggle search form
HackerRank Alien Languages Problem Solution

HackerRank Alien Languages Problem Solution

Posted on July 2, 2023July 2, 2023 By Yashwant Parihar No Comments on HackerRank Alien Languages Problem Solution

In this post, we will solve HackerRank Alien Languages Problem Solution.

Sophia has discovered several alien languages. Suprisingly, all of these languages have an alphabet, and each of them may contain thousands of characters! Also, all the words in a language have the same number of characters in it.
However, the aliens like their words to be aesthetically pleasing, which for them means that for the ith letter of an n-letter alphabet (letters are indexed 1… n):
if 2i > n. then the ith letter may be the last letter of a word, or it may be immediately followed by any letter, including itself.
if 2i 2i.
Sophia wants to know how many different words exist in this language. Since the result may be large, she wants to know this number, modulo 100000007(10 power 8 +7).
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.

Sample Input

3
1 3
2 3
3 2

Sample Output

1
3
6

Explanation
For the first test case, there’s one letter (‘a’) and all the words consist of 3 letters. There’s only one possibility which is “aaa”.
For the second test case, there are two letters (‘a’ and ‘b’) and all the words are of 3 letters. The possible strings are “abb”, “bab”. & “bbb”. The words can end only with ‘b’ because 2. index(b) = 2.2 > 2 and for ‘a’, it’s 2 index(a) = 2.1 ≤ 2. “aab” is not allowed because ‘a’ can not be followed immediately by ‘a’. For a word of length 4 and alphabet of size 2, “abab” would be allowed.
For the third test case, there are three letters (‘a’, ‘b’ and ‘C’) and all of the words are 2 letters. The words can only end with ‘b’ or ‘c’. The possible words are “ab”, “ac”, “bb”, “cc”, “bc”, “cb”.

HackerRank Alien Languages Problem Solution
HackerRank Alien Languages Problem Solution

Table of Contents

  • Alien Languages C Solution
  • Alien Languages C++ Solution
  • Alien Languages C Sharp Solution
  • Alien Languages Java Solution
  • Alien Languages Python Solution

Alien Languages C Solution

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

Alien Languages C++ Solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ULL;

ULL MOD = 100000007;
int N, M;

void Update(vector<ULL> &bit, int x, ULL val)
{
    for(x++; x < bit.size(); x += x&-x)
    {
        bit[x] = (bit[x] + val) % MOD;
    }
}

ULL Query(vector<ULL> &bit, int x)
{
    ULL res = 0;

    for(x++; x > 0; x -= x&-x)
    {
        res = (res + bit[x]) % MOD;
    }
    return res;
}

ULL Solve()
{
    if(M == 1)
    {
        return N / 2;
    }        
    ULL top = 1;
    ULL half = (N / 2) + (N % 2);    
    ULL DP[half + 3] = {0};
    ULL prev[half + 3] = {0};    

    DP[half + 2] = half;
    prev[1] = 1;
    // prev[1]
    

    for(int size = 2; size <= M; size++)
    {        
        ULL high = DP[half + 2];
        ULL add = DP[half / 2 + 2] - DP[half / 4];

        cerr << size << ": " << high << " (" << add << ")\n";

        int i;

        

        for(i = 1; 2 * i <= N; i++)
        {                           
            ULL a;
                        
            if(2 * i > half) 
            {                                                
                ULL diff = half - i;         
                
                a = (N % 2 == 0)
                  ? (diff + 1) + ((top * 2) * diff) % MOD 
                  : ((top * 2) * diff) % MOD;
                  
                a = (a + (top * 2 * (diff * (diff - 1) / 2)) % MOD) % MOD;

                cerr << "\t[" << i << "]: " << a << "\n";;   

                DP[i + 1] = (DP[i] + a) % MOD;   
                i++;                  
                break;                
            }
            else 
            {             
                a = DP[half + 2];
                
                // if(a * 2 <= half / 2 + 1) 
                a -= DP[i * 2];
                // else a -= DP[i + 2];
            }
            DP[i + 1] = (DP[i] + a) % MOD;

            cerr << "\t[" << i << "]: " << a << " (" << add << ")\n";;            
        }        
        prev[size] = top;
        top = high;        

        DP[half + 2] = (DP[i] + (high * half)) % MOD;
        // DP[i + 2] = DP[i + 1];
    }    
    ULL res = DP[half + 2];        

    return (res < 0) ? res + MOD : res;
}

ULL SOLVE()
{
    if(M == 1)
    {
        return N / 2;
    }
    ULL res = 0;

    // vector<vector<ULL>> DP(M + 1, vector<ULL>(N + 2, 0));

    vector<ULL> prev(N + 2, 0);

    for(ULL i = 1; i <= N; i++)
    {        
        // break;
        if(i * 2 > N) Update(prev, i, 1);
    }

    // Update(prev, N / 2 + 1, N / 2 + 1);

    ULL top = 1;
    ULL half = N / 2 + 1;//(N % 2);

    for(int size = 2; size <= M; size++)
    {        
        vector<ULL> next(N + 2, 0);

        ULL high = Query(prev, N);

        cerr << size << ": " << high << "\n";        

        for(int i = 1; i <= N; i++)
        {                           
            ULL a;

            if(2 * i <= N)
            {                
                a = (high - Query(prev, i * 2 - 1)) % MOD;
                                
                Update(next, i, a);                            
            }
            else 
            {              
                a = high;

                Update(next, i, a);
            }

            cerr << "\t[" << i << "]: " << a << "\n";;            
        }                
        prev = move(next);        
    }
    res = Query(prev, N);
    
    if(res < 0) res += MOD;

    return res;
}
/*
1
    _ 2 

    
*/

/*

9

1:
    5
    6
    7
    8
    9

2:
    1 5
    2 5

    1 6
    2 6
    3 6

    1 7
    2 7
    3 7

    1 8
    2 8
    3 8
    4 8

    1 9
    2 9
    3 9
    4 9

3:
    1 2 5

    1 2 6
    1 3 6

    1 2 7
    1 3 7

    1 2 8
    1 3 8
    1 4 8
    2 4 8        

    1 2 9
    1 3 9
    1 4 9
    2 4 9

4:
    1 2 4 8
    1 2 4 9

1
    _ 2 3 4|5 6 7 8 9
2
    _ _ _ 4|5 6 7 8 9
3
    _ _ _ _|_ 6 7 8 9
4
    _ _ _ _|_ _ _ 8 9

*/

ULL _Solve()
{
    vector<vector<ULL>> DP(20, vector<ULL>(N + 1, 0));
    vector<ULL> counts(20, 0);

    for(int i = N / 2 + 1; i <= N; i++)
    {
        DP[1][i] = DP[1][i - 1] + 1;
    }    
    counts[1] = DP[1][N];

    ULL p = 2;

    for(int size = 2; size < 20; size++)
    {
        // cerr << size << "\n";

        for(int j = 1; j <= N; j++)
        {           
            if(j * 2 > N)
            {
                DP[size][j] = (DP[size][j - 1]) % MOD;

                continue;
            }

            ULL sum = DP[size - 1][N] - DP[size - 1][j * 2 - 1];

            DP[size][j] = (DP[size][j - 1] + sum) % MOD;
        }             
        counts[size] = DP[size][N];

        continue;

        cerr << size << ": " << counts[size] << "\n";

        for(int j = 1; j <= N; j++)
        {
            if(DP[size][j])
            {
                cerr << "\t" << j << ": " << DP[size][j] - DP[size][j - 1] << "\n";                
            }
        }
        p *= 2;                   
    }

    vector<ULL> result(M + 1, 0);

    result[0] = 1;

    for(int size = 1; size <= M; size++)
    {
        for(int i = 1; i < 16 && size - i >= 0; i++)
        {
            result[size] = (result[size] + result[size - i] * counts[i]) % MOD;           
        }        
    }    
    return (result[M] < 0) ? result[M] + MOD : result[M];


    return 0;
}

int main()
{
    int t;
    cin >> t;

    while(t--)
    {
        cin >> N >> M;

        cout << _Solve() << "\n";

        continue;

        cout << Solve() << "\n";
        cout << SOLVE() << "\n";

        // memo = vector<vector<ULL>>(M + 1, vector<ULL>(N + 1, -1));
        // cout << Naive(0, N) << "\n";
    }
}
// 5000
// 43750000
// 29143101
// 96187357
// 95307470

Alien Languages C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace Solution {
class Solution {
    const ulong prime = 100000007UL;
    static void Main(string[] args) {
        int t = Convert.ToInt32(Console.ReadLine());
        for(int i = 0; i < t; ++ i)
        {
            string[] str = Console.ReadLine().Split(' ');
            ulong n = Convert.ToUInt64(str[0]);
            ulong m = Convert.ToUInt64(str[1]);
            Console.WriteLine(Solve(n,m));
        }
        /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    }
    
        static ulong Solve(ulong n, ulong m)
        {
            ulong[,] arr = new ulong[2, n + 1];
            var k = n % 2 + n / 2;
            var fac = new List<ulong> { k };
            for (var i = 1UL; i <= n / 2; ++i) arr[0, i] = (2 * i <= n / 2) ? k : n + 1 - 2 * i;
            k = n / 2;
            for ( ulong i = 0UL; k > 0 ;k /=2, i++)
            {
                ulong val = 0, q = i % 2;
                for (ulong j = k; j > 1; -- j)
                {
                    val = (val + arr[q, j]) % prime;
                    arr[1 - q, j / 2] = val;
                }
                fac.Add((arr[0, 1] + arr[1, 1]) % prime);
                arr[q, 1] = 0;
            }
            ulong[] res = new ulong[fac.Count];
            res[0] = 1;
            for( ulong i = 0; i < m; ++ i)
            {
                ulong ans = 0;
                for (int j = 0; j < res.Length; ++j) ans += (res[j] * fac[j]) % prime;
                Array.ConstrainedCopy(res, 0, res, 1, res.Length - 1);
                res[0] = ans % prime;
            }
            return res[0];
        }
}
}

Alien Languages Java Solution

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

Alien Languages Python Solution

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])
c, C#, C++, HackerRank Solutions, java, javascript, python Tags:C, cpp, CSharp, Hackerrank Solutions, java, javascript, python

Post navigation

Previous Post: HackerRank Brick Tiling Problem Solution
Next Post: HackerRank Stock Maximize Problem Solution

Related Posts

HackerRank Lucky Numbers Problem Solution HackerRank Lucky Numbers Problem Solution c
HackerRank Marc's Cakewalk Problem Solution HackerRank Marc’s Cakewalk Problem Solution c
HackerRank Dijkstra: Shortest Reach 2 Problem Solution HackerRank Dijkstra: Shortest Reach 2 Solution c
HackerRank Abbreviation Problem Solution HackerRank Abbreviation Problem Solution c
HackerRank Jumping on the Clouds Problem Solution HackerRank Jumping on the Clouds Solution c
HackerRank-Mini-Max-Sum-Problem-Solution HackerRank Mini-Max Sum Problem Solution c

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Pick Your Subject
Human Values

Copyright © 2023 TheCScience.

Powered by PressBook Grid Blogs theme