Table of Contents
King and Four Sons – 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++ replace HackerRank Solution
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i = (a); i <= (b); ++i)
#define FORD(i,a,b) for(int i = (a); i >= (b); --i)
#define RI(i,n) FOR(i,1,(n))
#define REP(i,n) FOR(i,0,(n)-1)
#define mini(a,b) a=min(a,b)
#define maxi(a,b) a=max(a,b)
#define mp make_pair
#define pb push_back
#define st first
#define nd second
#define sz(w) (int) w.size()
typedef vector<int> vi;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int inf = 1e9 + 5;
const int nax = 1e6 + 5;
const int mod = 1e9 + 7;
pii mul(pii a, pii b) {
ll c = (ll) a.st * b.st - (ll) a.nd * b.nd;
ll d = (ll) a.st * b.nd + (ll) a.nd * b.st;
c %= mod;
d %= mod;
if(c < 0) c += mod;
if(d < 0) d += mod;
return mp((int) c, (int) d);
}
pii pw(pii a, int k) {
pii r = mp(1, 0);
while(k) {
if(k % 2) r = mul(r, a);
a = mul(a, a);
k /= 2;
}
return r;
}
int pw(int a, int k) {
int r = 1;
while(k) {
if(k % 2) r = (ll) r * a % mod;
a = (ll) a * a % mod;
k /= 2;
}
return r;
}
int f(int n) {
int r = pw(mp(1,mod-1), n).st + pw(mp(1,1), n).st;
r %= mod;
r += pw(2, n);
r %= mod;
r = (ll) r * pw(4, mod - 2) % mod;
return r;
}
int dp[105];
int main() {
int n, k;
scanf("%d%d", &n, &k);
dp[0] = 1;
REP(_, n) {
int a;
scanf("%d", &a);
a = f(a);
FORD(j, k, 1)
dp[j] = (dp[j] + (ll) dp[j-1] * a) % mod;
}
printf("%d\n", dp[k]);
return 0;
}
Java rep HackerRank Solution
import java.io.*;
import java.util.*;
public class Solution {
private static InputReader in;
private static PrintWriter out;
public static long mod = 1000000007;
public static long INV4 = pow(new Complex(4,0), mod-2).a;
static class Complex {
public long a,b;
public Complex(long a, long b) {
this.a = a;
this.b = b;
if (a < 0) a += mod;
}
public Complex multiply(Complex other) {
return new Complex((a * other.a + mod - (b * other.b % mod)) % mod, (a * other.b + b * other.a) % mod);
}
}
public static Complex pow(Complex a, long e) {
Complex r = new Complex(1,0);
while(e>0) {
if ((e&1)==1) r = r.multiply(a);
a = a.multiply(a);
e >>= 1;
}
return r;
}
public static long nways(long x) {
Complex s1 = pow(new Complex(1, 1), x);
Complex s2 = pow(new Complex(1, mod - 1), x);
Complex s3 = pow(new Complex(2, 0), x);
long res = (s3.a + s1.a + s2.a) % mod;
return res * INV4 % mod;
}
public static void main(String[] args) throws IOException {
in = new InputReader(System.in);
out = new PrintWriter(System.out, true);
int n = in.nextInt();
int k = in.nextInt();
long[] dp = new long[k+1];
dp[0] = 1;
for (int i = 0; i < n; i++) {
long m = nways(in.nextInt());
long[] next = new long[k+1];
System.arraycopy(dp, 0, next, 0, k+1);
for (int j = 0; j < k; j++) {
next[j+1] = (next[j+1] + dp[j] * m) % mod;
}
dp = next;
}
out.println(dp[k]);
out.close();
System.exit(0);
}
static class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
}
Python 3 rep HackerRank Solution
#!/bin/python3
import os
import sys
from functools import reduce
from itertools import combinations
#
# Complete the king function below.
#
cc = 10**9 + 7
d30 = 73741817
D2 = 976371285
D3 = 688423210
D4 = 905611805
D5 = 607723520
D6 = 235042059
D7 = 255718402
D8 = 494499948
def twopower(a):
if a < 30:
return (2**a)
elif a >= 30 and a <100:
dvi = a//30
rem = a%30
ans = ((d30**dvi)%cc) * ((2**rem)%cc)
ans = ans%cc
return (ans)
elif a >= 100 and a <= 1000:
dvi2 = a//100
dvi = a%100//30
rem = a%100%30
ans = ((D2**dvi2)%cc) * ((d30**dvi)%cc)*((2**rem)%cc)
ans = ans%cc
return (ans)
def midpower(a):
if a <= 1000:
return (twopower(a))
elif a > 1000 and a <= 10**4:
x = a //1000
y = a % 1000
z = ((D3**x)%cc) * twopower(y)
z = z%cc
return (z)
elif a >10**4 and a <= 10**5:
x1 = a // 10**4
x2 = a // 10**3 - x1*10
y = a % 10**3
z = ((D4**x1)%cc) * ((D3**x2)%cc) * twopower(y)
z = z % cc
return (z)
elif a >10**5 and a <= 10**6:
x1 = a // 10**5
x2 = a // 10**4 - x1*10
x3 = a // 10**3 - x2*10 - x1*100
y = a % 10**3
z = ((D5**x1)%cc) * ((D4**x2)%cc) * ((D3**x3)%cc) * twopower(y)
z = z % cc
return (z)
def hipower(a):
if a <= 10**6:
return (midpower(a))
elif a > 10**6 and a <= 10**7:
x = a //10**6
y = a % 10**6
z = ((D6**x)%cc) * midpower(y)
z = z%cc
return (z)
elif a >10**7 and a <= 10**8:
x1 = a // 10**7
x2 = a // 10**6 - x1*10
y = a % 10**6
z = ((D7**x1)%cc) * ((D6**x2)%cc) * midpower(y)
z = z % cc
return (z)
elif a >10**8 and a <= 10**9:
x1 = a // 10**8
x2 = a // 10**7 - x1*10
x3 = a // 10**6 - x2*10 - x1 *100
y = a % 10**6
z = ((D8**x1)%cc) * ((D7**x2)%cc) * ((D6**x3)%cc) * midpower(y)
z = z % cc
return (z)
def fanum(a):
if a%4 == 0 or a%4 == 1:
if (a//4) % 2 == 0:
return (int(hipower(a-2)+hipower(2*(a//4)-1)))
else:
return (int(hipower(a-2)-hipower(2*(a//4)-1)))
elif a%4 == 3:
if (a//4) % 2 == 0:
return (int(hipower(a-2) - hipower(2*(a//4))))
else:
return (int(hipower(a-2) + hipower(2*(a//4))))
elif a%4 == 2:
return (int(hipower(a-2)))
def king(army, k):
lst = []
for i in army:
lst.append(fanum(i))
lst1 = []
lst1.append(lst)
for i in range(1,k):
l = []
el = 0
for j in range(i,n):
el = (el + lst1[i-1][j-i])%cc
l.append((el*lst[j])%cc)
lst1.append(l)
tt = sum(lst1[-1])
return(tt%cc)
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
nk = input().split()
n = int(nk[0])
k = int(nk[1])
army = list(map(int, input().rstrip().split()))
result = king(army, k)
fptr.write(str(result) + '\n')
fptr.close()
Python 2 rep HackerRank Solution
import itertools, math
MOD=int(1e9+7)
def S_(n,k):
def cnk(n,k):
return int(math.factorial(n)/(math.factorial(k)*math.factorial(n-k)))
return sum(cnk(n,i) for i in xrange(k,n+1,4))%MOD
ans=[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]]
def S(n,k=0):
if n<5:
return sum(ans[n][k::4])
r=0
r=pow(2,n-2,MOD)-pow(2,n/2,MOD)
if n&1:
r=(r+pow(2,(n-3)/2,MOD)*sum(ans[3][(k-(n-3)/2)%4::4]))%MOD
else:
r=(r+pow(2,(n-3)/2,MOD)*sum(ans[4][(k-(n-3)/2)%4::4]))%MOD
return int(r)
# for n in (100,101):
# for k in xrange(4):
# s_,s=S_(n,k),S(n,k)
# print "---",n,k,s_==s,s_,s
# exit()
n,k=map(int,raw_input().split())
a=map(int,raw_input().split())
det=[S(i) for i in a]
# s=0
# for comb in itertools.combinations(range(n),k):
# tot=1
# for i in comb:
# tot=(tot*det[i])%MOD
# s=(s+tot)%MOD
# print s
mem=[[float("+inf")]*(i+1) for i in xrange(n+1)]
mem[0][0]=1
for i in xrange(1,n+1):
mem[i][1] = sum(det[:i])%MOD
mem[i][i] = (mem[i-1][i-1]*det[i-1])%MOD
for i in xrange(3,n+1):
for j in xrange(2,min(i,k+1)):
mem[i][j] = (mem[i-1][j] + mem[i-1][j-1]*det[i-1])%MOD
print mem[n][k]
C rep HackerRank Solution
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MOD 1000000007
void one(long long*a,int SIZE);
void mul(long long*a,long long*b,int SIZE);
void powm(long long*a,int n,long long*res,int SIZE);
int a[10000];
long long dp[101][10001]={0},b[10000],B[4][4],C[4][4],A[4][4]={
{1,0,0,1},
{1,1,0,0},
{0,1,1,0},
{0,0,1,1}
},aa[4]={1,1,0,0};
int main(){
int N,K,i,j;
scanf("%d%d",&N,&K);
for(i=0;i<N;i++)
scanf("%d",a+i);
for(i=0;i<N;i++)
if(!a[i])
b[i]=1;
else{
memcpy(B,A,sizeof(B));
powm(&B[0][0],a[i]-1,&C[0][0],4);
for(j=b[i]=0;j<4;j++)
b[i]=(b[i]+aa[j]*C[0][j])%MOD;
}
dp[0][0]=1;
for(i=0;i<N;i++)
for(j=0;j<=K;j++)
if(j)
dp[j][i+1]=(dp[j][i]+dp[j-1][i]*b[i])%MOD;
else
dp[j][i+1]=dp[j][i];
printf("%lld",dp[K][N]);
return 0;
}
void one(long long*a,int SIZE){
int i,j;
for (i = 0; i < SIZE; i++)
for (j = 0; j < SIZE; j++)
a[i*SIZE+j] = (i == j);
return;
}
void mul(long long*a,long long*b,int SIZE){
int i,j,k;
long long res[SIZE][SIZE];
for(i=0;i<SIZE;i++)
for(j=0;j<SIZE;j++)
res[i][j]=0;
for (i = 0; i < SIZE; i++)
for (j = 0; j < SIZE; j++)
for (k = 0; k < SIZE; k++)
res[i][j] = (res[i][j]+a[i*SIZE+k] * b[k*SIZE+j])%MOD;
for (i = 0; i < SIZE; i++)
for (j = 0; j < SIZE; j++)
a[i*SIZE+j] = res[i][j];
return;
}
void powm(long long*a,int n,long long*res,int SIZE){
one(res,SIZE);
while (n > 0) {
if (n % 2 == 0)
{
mul(a, a,SIZE);
n /= 2;
}
else {
mul(res, a,SIZE);
n--;
}
}
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
