Find the Seed – 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 <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll MOD = 1000000007;
ll powe(ll a, ll b) {
if (b == 0) return 1;
if (b % 2 == 0) return powe( (a*a)%MOD, b/2);
return (a*powe(a, b-1)) % MOD;
}
ll inv(ll a) {
return powe(a, MOD-2);
}
struct matrix {
vector<vector<ll>> M;
matrix I() const {
matrix ans;
ans.M = M;
for (int i = 0; i < M.size(); ++i)
for (int j = 0; j < M.size(); ++j)
ans.M[i][j] = !!(i==j);
return ans;
}
matrix operator*(const matrix& rhs) const {
matrix ans;
ans.M = M;
int N = M.size();
for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) {
ans.M[i][j] = 0;
for (int k = 0; k < N; ++k)
ans.M[i][j] = (ans.M[i][j] + M[i][k]*rhs.M[k][j]) % MOD;
}
return ans;
}
};
matrix powm(const matrix& M, int b) {
if (b == 0) return M.I();
if (b % 2 == 0) return powm( M*M, b/2);
return M*powm(M, b-1);
}
int main() {
ll N, K;
cin >> N >> K;
vector<ll> F(N);
for (ll &x : F) cin >> x;
vector<ll> C(N);
for (ll &x : C) cin >> x;
matrix M;
M.M = vector<vector<ll>>(N, vector<ll>(N));
for (int i = 0; i < N-1; ++i)
for (int j = 0; j < N; ++j)
M.M[i][j] = !!((i+1) == j);
ll cinv = inv(C.back());
M.M[N-1][0] = cinv;
for (int j = 1; j < N; ++j)
M.M[N-1][j] = ((MOD - C[j-1])*cinv)%MOD;
auto M2 = powm(M, K-N+1);
vector<ll> ans(N);
for (int i = 0; i < N; ++i) {
ans[i] = 0;
for (int j = 0; j < N; ++j)
ans[i] = (ans[i] + F[j]*M2.M[i][j]) % MOD;
}
for (int i = 0; i < N; ++i) {
if (i) printf(" ");
printf("%lld", ans[i]);
}
printf("\n");
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 inv(long N, long M) {
long x = 0, lastx = 1, y = 1, lasty = 0, q, t, a = N, b = M;
while (b != 0) {
q = a / b; t = a % b; a = b; b = t;
t = x; x = lastx - q * x; lastx = t;
t = y; y = lasty - q * y; lasty = t;
}
return (lastx + M) % M;
}
public static void main(String[] args) throws IOException {
in = new InputReader(System.in);
out = new PrintWriter(System.out, true);
int N = in.nextInt(), K = in.nextInt();
long[][] mat = new long[N][N];
long[] vec = new long[N];
long[] coef = new long[N];
for (int i = 0; i < N; i++) vec[i] = in.nextInt();
for (int i = 0; i < N; i++) coef[i] = in.nextInt();
for (int i = 0; i < N-1; i++) mat[i][i+1] = 1;
long iv = inv(coef[N-1], mod);
mat[N-1][0] = iv;
for (int i = 1; i < N; i++)
mat[N-1][i] = (mod - coef[i-1]) * iv % mod;
mat = mat_exp(mat, K - N + 1);
for (int i = 0; i < N; i++) {
long s = 0;
for (int j = 0; j < N; j++) {
s = (s + mat[i][j] * vec[j]) % mod;
}
if (i > 0) out.print(" ");
out.print(s);
}
out.println();
out.close();
System.exit(0);
}
private static long[][] mat_exp(long[][] A, int e) {
if (e == 0) {
long[][] ret = new long[A.length][A.length];
for (int i = 0; i < A.length; i++) ret[i][i] = 1;
return ret;
}
if (e == 1)
return A;
else if (e % 2 == 0) {
long[][] A1 = mat_exp(A, e / 2);
return matrix_mult(A1, A1);
} else
return matrix_mult(A, mat_exp(A, e - 1));
}
private static long[][] matrix_mult(long[][] A, long[][] B) {
long[][] C = new long[A.length][A.length];
for (int i = 0; i < A.length; i++)
for (int j = 0; j < A.length; j++)
for (int k = 0; k < A.length; k++)
C[i][k] = (C[i][k] + A[i][j] * B[j][k]) % mod;
return C;
}
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
MOD = 1000000007
def generalizedEuclidianAlgorithm(a, b):
if b > a:
return generalizedEuclidianAlgorithm(b,a);
elif b == 0:
return (1, 0);
else:
(x, y) = generalizedEuclidianAlgorithm(b, a % b);
return (y, x - (a // b) * y)
def inversemodp(a, p):
a = a % p
if (a == 0):
# print "a is 0 mod p"
return 0
(x,y) = generalizedEuclidianAlgorithm(p, a % p);
return y % p
def identitymatrix(n):
return [[int(x == y) for x in range(0, n)] for y in range(0, n)]
def multiply_vector_scalar(vector, scalar, q):
kq = []
for i in range (0, len(vector)):
kq.append (vector[i] * scalar %q)
return kq
def minus_vector_scalar1(vector1, scalar, vector2, q):
kq = []
for i in range (0, len(vector1)):
kq.append ((vector1[i] - scalar * vector2[i]) %q)
return kq
def inversematrix1(matrix, q):
n = len(matrix)
A =[]
for j in range (0, n):
temp = []
for i in range (0, n):
temp.append (matrix[j][i])
A.append(temp)
Ainv = identitymatrix(n)
for i in range(0, n):
factor = inversemodp(A[i][i], q)
A[i] = multiply_vector_scalar(A[i],factor,q)
Ainv[i] = multiply_vector_scalar(Ainv[i],factor,q)
for j in range(0, n):
if (i != j):
factor = A[j][i]
A[j] = minus_vector_scalar1(A[j],factor,A[i],q)
Ainv[j] = minus_vector_scalar1(Ainv[j],factor,Ainv[i],q)
return Ainv
def mult(x, y):
c = [[0 for _ in range(len(y[0]))] for _ in range(len(x))]
for i in range(len(x)):
for j in range(len(y[0])):
for k in range(len(x)):
c[i][j] += x[i][k] * y[k][j]
c[i][j] = c[i][j] % MOD
return c
def matpow(b, p):
if p == 0: return identitymatrix(n)
if p == 1: return b
if p % 2 == 1:
return mult(b, matpow(b, p - 1))
ret = matpow(b, p // 2)
return mult(ret, ret)
n, k = map(int, input().split())
arrk = list(map(int, input().split()))
arrc = list(map(int, input().split()))
left = [[x] for x in arrk];
middle = [[0 for _ in range(n)] for _ in range(n)]
middle[0] = list(arrc)
for i in range(1,n):
middle[i][i-1] = 1
inv = inversematrix1(middle, MOD)
inv = [[int(x) for x in y] for y in inv]
ans = matpow(inv, k - n + 1)
ans = mult(ans, left)
print(' '.join(map(lambda x : str(x[0]), ans)))
Python 2 rep HackerRank Solution
mod = 10**9+7
def mulmod(T,te,n):
res = [0 for _ in xrange(n)]
for i in range(n):
for j in range(n):
res[i] += T[i][j]*te[j]
res[i] %= mod
return res
def mul2mod(T1,T2,n):
res = [[0 for _ in xrange(n)] for _ in xrange(n)]
for i in range(n):
for j in range(n):
for k in range(n):
res[i][j] += T1[i][k]*T2[k][j]
res[i][j] %= mod
return res
def modexp(T,e,n):
res = [[0 for _ in xrange(n)] for _ in xrange(n)]
for i in range(n):
res[i][i] = 1
while e:
if e&1:
res = mul2mod(res,T,n)
T = mul2mod(T,T,n)
e /= 2
return res
def inversemodp(a, b):
res = 1
while b:
if b&1:
res *= a
res %= mod
b >>= 1
a = (a*a)%mod
return res
n,k = map(int,raw_input().split())
F = map(int,raw_input().split())
C = map(int,raw_input().split())
T = [[0 for _ in xrange(n)] for _ in xrange(n)]
for i in xrange(n):
T[0][i] = C[i]
for i in xrange(1,n):
T[i][i-1] = 1
T1 = [[0 for _ in xrange(n)] for _ in xrange(n)]
for i in xrange(n-1):
T1[i][i+1] = 1
for i in xrange(1,n):
T1[n-1][i] = mod-(T[0][i-1]*inversemodp(T[0][n-1],mod-2))%mod
T1[n-1][i] %= mod
T1[n-1][0] = inversemodp(T[0][n-1],mod-2)
#print T1
#print T
#F = F[::-1]
T1 = modexp(T1,k-n+1,n)
ans = mulmod(T1,F,n)
#ans = ans[::-1]
print ' '.join(map(str, ans))
#te = [1 for _ in xrange(n)]
#print mulmod(T,te,n)
C rep HackerRank Solution
#include <math.h>
#include <stdio.h>
#include <string.h>
#define maxn (110)
//const long long mod = 5;
long long mod = 1000000007;
long long n, k, result;
long long ca, cb;
long long tmp;
long long v[maxn], c[maxn], v2[maxn];
long long m[maxn][maxn];
long long res[2][maxn][maxn];
void solve(long long x, long long y) {
if (y == 0) {//x==1
//if (x != 1) printf("NO");
ca = 1;
cb = 0;
return;
}
solve(y, x % y);
tmp = x / y;
tmp = ca - tmp * cb;
tmp = ((tmp % mod) + mod) % mod;
ca = cb;
cb = tmp;
}
inline long long getI(long long now) {
solve(now, mod);
return ca;
}
inline void getM() {
memset(m, 0, sizeof(m));
for (int i = 1; i < n; ++i) m[i - 1][i] = 1;
long long cn = getI(c[n - 1]);
m[n - 1][0] = cn;
for (int i = 1; i < n; ++i) {
tmp = -cn * c[i - 1];
tmp = ((tmp % mod) + mod) % mod;
m[n - 1][i] = tmp;
}
}
void multiM(long long C[maxn][maxn], long long A[maxn][maxn], long long B[maxn][maxn]) {
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j) {
tmp = 0;
for (int k = 0; k < n; ++k) tmp = (tmp + A[i][k] * B[k][j]) % mod;
C[i][j] = tmp;
}
}
void printM(long long m[maxn][maxn]) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) printf(" %lld", m[i][j]);
printf("\n");
}
}
void calcM(long long po) {
if (po == 0) return;
calcM(po >> 1);
multiM(res[result ^ 1], res[result], res[result]);
result ^= 1;
if (po & 1) {
multiM(res[result ^ 1], res[result], m);
result ^= 1;
}
//printf("%d", po);
//printM(res[result]);
}
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
scanf("%lld%lld", &n, &k);
for (int i = 0; i < n; ++i) scanf("%lld", v + i);
for (int i = 0; i < n; ++i) scanf("%lld", c + i);
getM();
//printM(m);
memset(res, 0, sizeof(res));
result = 0;
for (int i = 0; i < n; ++i) res[0][i][i] = 1;
calcM(k - n + 1);
//printM(res[result]);
for (int i = 0; i < n; ++i) {
tmp = 0;
for (int j = 0; j < n; ++j) tmp = (tmp + res[result][i][j] * v[j]) % mod;
v2[i] = tmp;
}
printf("%lld", v2[0]);
for (int i = 1; i < n; ++i) printf(" %lld", v2[i]);
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
