Alien Languages – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Alien Languages HackerRank Solution
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#define mod 100000007
int a[500005];
inline void ADD(int & x, int y) {
x += y; if (x >= mod) x -= mod;
}
int S(int l, int r) {
int answer = 0;
for (int i = l; i <= r; i ++) {
ADD(answer, a[i]);
}
return answer;
}
void calc(int n, vector<int> & coeff) {
// lo: [1..n/2]
// hi: [n/2+1..n]
a[0] = 0;
for (int i = 1; i <= n; i ++) {
a[i] = 1;
}
coeff[1] = S(n/2+1, n);
for (int le = 2; coeff[le - 1] != 0; le ++) {
for (int i = 1; i <= n; i ++) ADD(a[i], a[i - 1]);
for (int i = n; i >= 1; i --) {
a[i] = a[i / 2];
}
coeff[le] = S(n/2+1, n);
}
}
int v[500005];
int main() {
int tc; cin >> tc;
for (; tc > 0; tc --) {
int n, m;
cin >> n >> m;
vector<int> coeff (22);
calc(n, coeff);
v[0] = 1;
for (int i = 1; i <= m; i ++) {
v[i] = 0;
for (int k = 0; k <= i and k <= 20; k ++) {
v[i] = (v[i] + (long long) v[i - k] * coeff[k]) % mod;
}
}
cout << v[m] << endl;
}
return 0;
}
Java Alien Languages HackerRank Solution
import java.awt.Point;
import java.io.*;
import java.math.BigInteger;
import java.util.*;
import static java.lang.Math.*;
public class Solution implements Runnable {
BufferedReader in;
PrintWriter out;
StringTokenizer tok = new StringTokenizer("");
public static void main(String[] args) {
new Thread(null, new Solution(), "", 256 * (1L << 20)).start();
}
public void run() {
try {
long t1 = System.currentTimeMillis();
out = new PrintWriter(System.out);
in = new BufferedReader(new InputStreamReader(System.in));
//in = new BufferedReader(new FileReader("src/input.txt"));
// out = new PrintWriter("output.txt");
Locale.setDefault(Locale.US);
solve();
in.close();
out.close();
long t2 = System.currentTimeMillis();
System.err.println("Time = " + (t2 - t1));
} catch (Throwable t) {
t.printStackTrace(System.err);
System.exit(-1);
}
}
String readString() throws IOException {
while (!tok.hasMoreTokens()) {
tok = new StringTokenizer(in.readLine());
}
return tok.nextToken();
}
int readInt() throws IOException {
return Integer.parseInt(readString());
}
long readLong() throws IOException {
return Long.parseLong(readString());
}
double readDouble() throws IOException {
return Double.parseDouble(readString());
}
// solution
void solve() throws IOException {
int ct = readInt();
while (ct-- > 0) {
solveTestCase();
}
}
static final long modulo = 100000007L;
void solveTestCase() throws IOException {
int n = readInt();
int wordLength = readInt();
int maxLength = (int) (1 + Math.ceil(Math.log(n) / Math.log(2))); //science!
FenwickTree[] f = new FenwickTree[maxLength + 1];
for (int i = 0; i < f.length; i++) {
f[i] = new FenwickTree(n);
}
f[0].increase(0, +1);
for (int i = 1; i <= n; i++) {
f[1].increase(i, +1);
}
for (int curSymbol = 1; curSymbol <= n; curSymbol++) {
for (int curLength = 2; curLength <= maxLength; curLength++) {
long value = f[curLength - 1].find(curSymbol / 2);
f[curLength].increase(curSymbol, +value);
}
}
long[] wordsWithLength = new long[maxLength + 1];
for (int lastSymbol = 0; lastSymbol <= n; lastSymbol++) {
if (lastSymbol * 2 > n) {
for (int length = 1; length <= maxLength; length++) {
wordsWithLength[length] = (wordsWithLength[length] + f[length].find(lastSymbol) - f[length].find(lastSymbol - 1)) % modulo;
}
}
}
// System.out.println(Arrays.toString(wordsWithLength) + " wwl");
long[] result = new long[wordLength + 1];
result[0] = 1;
for (int i = 0; i < result.length; i++) {
for (int nextWordLength = 1; nextWordLength <= maxLength; nextWordLength++) {
if (i + nextWordLength < result.length) {
result[i + nextWordLength] = (result[i + nextWordLength] + result[i] * wordsWithLength[nextWordLength]) % modulo;
}
}
}
out.println(result[wordLength]);
}
class FenwickTree {
private long[] sum;
FenwickTree(int size) {
sum = new long[size + 2];
}
private int prev(int x) {
return x & (x - 1);
}
private int next(int x) {
return 2 * x - prev(x);
}
void increase(int id, long value) {
id++;
while (id < sum.length) {
sum[id] = (sum[id] + value) % modulo;
id = next(id);
}
}
long find(int id) {
id++;
long res = 0;
if (id == 0) {
return 0;
}
while (id > 0) {
res += sum[id];
id = prev(id);
}
return res % modulo;
}
}
}
//ABC
Python 3 rep HackerRank Solution
# Enter your code here. Read input from STDIN. Print output to STDOUT
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])
Python 2 Alien Languages HackerRank Solution
from numpy import matrix
def monoidpow(op,e,a,k):
sq = a
c = e
while k>0:
if k&1: c = op(c,sq)
sq = op(sq,sq)
k>>=1
return c
for _ in xrange(input()):
N,M = map(int,raw_input().split())
F = [[0]*20 for _ in xrange(N+1)]
for i in xrange(N,N/2,-1): F[i][0] = 1
F[N/2][1] = 1+N%2
for i in xrange(N/2-1,0,-1):
for k in xrange(1,20):
F[i][k]+=(F[2*i][k-1] + F[2*i+1][k-1] + F[i+1][k])%100000007
S = [0]*20
for j in xrange(1,N+1):
for k in xrange(20):
S[k] =(S[k]+F[j][k])%100000007
A = matrix([S]+[[i==j for i in xrange(20)] for j in xrange(19)],dtype='longlong')
A = monoidpow(lambda a,b: a*b%100000007,1,A,M)
print (A*matrix([[1]]+[[0]]*19))[0,0]
C Alien Languages HackerRank Solution
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main() {
int tpm, nbtest,nb,profondeur,i,j,tot,deb,*facteur,*list,*previous,*next,*tmp,mod=100000007,flnb_2,flnb_2p1,out;
scanf("%d", &nbtest);
while(nbtest>0){
nbtest--;
scanf("%d %d", &nb,&profondeur);
facteur=(int*) calloc(profondeur,sizeof(int));
list=(int*) calloc(profondeur,sizeof(int));
previous=(int*) calloc(nb+1,sizeof(int));
next=(int*) calloc(nb+1,sizeof(int));
flnb_2=floor(nb/2);
flnb_2p1=flnb_2+1;
out=0;
for(i=1;i<=nb;i++){
previous[i]=1;
}
tot=nb-flnb_2;
for(j=1;j<profondeur;j++){
list[j]=tot;
next[1]=tot;
//printf("\n");
//printf("\n");
for(i=1;i<=j-1;i++){
//printf("tot => %d - %d x %d ",tot ,facteur[i],list[j-i]);
tot-=((long long)facteur[i]*(long long)list[j-i])%mod;
if(tot<0){
tot+=mod;
}
//printf(" => %d",tot);
}
//printf("\n");
//printf("\n");
if(tot>0){
facteur[j]=tot;
} else {
out=1;
/*
printf("\n"); printf("\n");
for(i=1;i<j;i++){
printf("%d ",facteur[i]);
}
printf("\n");
for(i=1;i<j;i++){
printf("%d ",list[i]);
}
printf("out");*/
break;
}
tot=0;
for(i=2;i<flnb_2p1;i=i+2){
next[i]=(next[i-1]+previous[i>>1])%mod;
next[i+1]=next[i];
}
if(flnb_2p1&1){
deb=1;
tot=(tot+next[flnb_2p1])%mod;
} else {
deb=0;
}
for(i=flnb_2p1+deb;i<=nb;i=i+2){
next[i]=(next[i-1]+previous[i>>1])%mod;
if(i+1<=nb){
next[i+1]=next[i]%mod;
tot=(tot+2*next[i])%mod;
} else {
tot=(tot+next[i])%mod;
}
}
//for(i=1;i<=nb;i=i+1){printf("%d\t",next[i]);}
//printf("\n\n");
tmp=previous;
previous=next;
next=tmp;
}
if(out&1){
for(i=j+1;i<=profondeur;i++){
list[i]=0;
for(int k=1;k<=j;k++){
tot=((long long)facteur[k]*(long long)list[i-k])%mod;
//printf("Tot: %d %d => %d + %d\n",facteur[k],list[i-k],tot,list[i]);
list[i]=(list[i]+tot)%mod;
}
}
tot=list[i-1];
}
printf("%d\n", tot);
}
return 0;
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below