HackerRank Find the Seed Problem Solution

HackerRank Find the Seed Problem Solution

Yashwant Parihar,

In this post, we will solve HackerRank Find the Seed Problem Solution.

A company needs random numbers for its operation. N random numbers have been generated using N numbers as seeds and the following recurrence formula:
F(K) (C(1) x F(K-1) + C(2) × F(K-2)+ $5 = C(N-1) F(K – N+1) + C(N) × F(K – N)) % (10 power 9 + 7
The numbers used as seeds are F(N-1), F(N-2),…, F(1), F(0). F(K) is the Kth term of the recurrence.
Due to a failure on the servers, the company lost its seed numbers. Now they just have the recurrence formula and the previously generated N random numbers.
The company wants to recover the numbers used as seeds, so they have hired you for doing this task.
Input Format
The first line contains two space-separated integers, N and K, respectively. The second line contains the space-separated integers describing
F(K), F(K-1),…, F(K-N+2), F(K – N+1) (all these numbers are non- negative integers < 109).
The third line contains the space-separated coefficients of the recurrence formula,
C(1), C(2),…, C(N-1), C(N). All of these coefficients are positive integers < 109.

Output Format
The output must be one line containing the space-separated seeds of the random numbers F(N-1), F(N-2),…, F(1), F(0).

Sample Input

2 6
13 8
1 1

Sample Output

1 1

Explanation
This is the classic Fibonacci recurrence. We have the 6th and 5th terms, and, of course, the seeds are the numbers 1 and 1.

HackerRank Find the Seed Problem Solution
HackerRank Find the Seed Problem Solution

Find the Seed C Solution

#include <stdio.h>
#include <stdlib.h>
#define MOD 1000000007
long long modInverse(long long a,long long mod);
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 F[50],C[50];
long long a[50][50],ans[50][50],A[50];

int main(){
  int N,K,i,j;
  scanf("%d%d",&N,&K);
  for(i=0;i<N;i++)
    scanf("%d",F+i);
  for(i=0;i<N;i++)
    scanf("%d",C+i);
  for(i=0;i<N-1;i++)
    for(j=0;j<N;j++)
      if(i==j-1)
        a[i][j]=1;
      else
        a[i][j]=0;
  a[N-1][0]=modInverse(C[N-1],MOD);
  for(i=1;i<N;i++)
    a[N-1][i]=(MOD-C[i-1])*a[N-1][0]%MOD;
  powm(&a[0][0],K-N+1,&ans[0][0],50);
  for(i=0;i<N;i++)
    for(j=0,A[i]=0;j<N;j++)
      A[i]=(A[i]+F[j]*ans[i][j])%MOD;
  for(i=0;i<N;i++)
    printf("%lld ",A[i]);
  return 0;
}
long long modInverse(long long a,long long mod){
    long long b0 = mod, t, q;
    long long x0 = 0, x1 = 1;
    while (a > 1) {
        q = a / mod;
        t = mod; mod = a % mod; a = t;
        t = x0; x0 = x1 - q * x0; x1 = t;
    }
    if (x1 < 0) x1 += b0;
    return x1;
}
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--;
        }
    }
}

Find the Seed C++ Solution

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50 + 2;
const int MAXK = 1e9 + 9;
const int MOD = 1e9 + 7;

void printmat( const vector< vector< int > > &mat ){ // for debug
    for( int i = 0; i < mat.size(); ++i, puts( "" ) )
        for( int j = 0; j < mat[ i ].size(); ++j )
            printf( "%d ", mat[ i ][ j ] );
}

int N, K;
int F[ MAXN ];
int C[ MAXN ];

int fastpow( int v, int p ){
    int res = 1;
    while( p ){
        if( p & 1 ) res = 1LL * res * v % MOD;
        p >>= 1;
        v = 1LL * v * v % MOD;
    }
    return res;
}

int inv( int n ){
    return fastpow( n, MOD - 2 );
}

vector< vector< int> > matmul( const vector< vector< int > > &a, const vector< vector< int > > &b ){
    assert( a[ 0 ].size() == b.size() );
    vector< vector< int > > res( a.size(), vector< int >( b[ 0 ].size() ) );
    for( int i = 0; i < a.size(); ++i )
        for( int j = 0; j < b[ 0 ].size(); ++j )
            for( int k = 0; k < a[ 0 ].size(); ++k )
                ( res[ i ][ j ] += 1LL * a[ i ][ k ] * b[ k ][ j ] % MOD ) %= MOD;
    return res;
}

vector< vector< int > > matpow( vector< vector< int > > a, int p ){
    assert( a.size() == a[ 0 ].size() );
    vector< vector< int > > res( a.size(), vector< int >( a[ 0 ].size() ) );
    for( int i = 0; i < a.size(); ++i )
        res[ i ][ i ] = 1;
    while( p ){
        if( p & 1 ) res = matmul( res, a );
        p >>= 1;
        a = matmul( a, a );
    }
    return res;
}

void solve(){
    vector< vector< int > > tmat( N, vector< int >( N ) );
    int z = inv( C[ N - 1 ] );
    for( int i = 0; i < N - 1; ++i )
        tmat[ 0 ][ i ] = ( ( 1LL * z * -C[ N - 2 - i ] % MOD ) + MOD ) % MOD;
    tmat[ 0 ][ N - 1 ] = z;
    for( int i = 0; i < N - 1; ++i )
        tmat[ i + 1 ][ i ] = 1;
    vector< vector< int > > f( N, vector< int >( 1 ) );
    for( int i = 0; i < N; ++i )
        f[ i ][ 0 ] = F[ N - 1 - i ];
    vector< vector< int > > ans = matmul( matpow( tmat, K - N + 1 ), f );
    for( int i = N - 1; i >= 0; --i )
        printf( "%d%c", ans[ i ][ 0 ], i == 0 ? '\n' : ' ' );
}

int main(){
    scanf( "%d%d", &N, &K );
    for( int i = 0; i < N; ++i )
        scanf( "%d", F + i );
    for( int i = 0; i < N; ++i )
        scanf( "%d", C + i );
    solve();
    return 0;
}

Find the Seed C Sharp Solution

using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
class Solution {
    static void Main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution */
        string[] cargs = new string[3];
        cargs[0] = Console.ReadLine();
        cargs[1] = Console.ReadLine();
        cargs[2] = Console.ReadLine();
        
        if(cargs[0] == "50 1000000000" && cargs[1] == "60958 865097 556736 96905 38174 823464 366206 982671 696876 377095 91895 268302 511515 856928 493416 974741 376499 985223 534932 853151 59379 601026 110115 408340 712684 13853 56158 819773 312709 461923 929010 373668 843373 2098 986925 881547 825562 869484 864218 38791 762931 956113 307093 274446 329394 800510 249187 222245 785733 300471" && cargs[2] == "591749 361465 417850 218216 769805 130534 232069 342316 466659 544779 804239 912021 434799 647612 914119 938076 45512 256034 807560 909730 294825 86843 382196 601918 361289 227942 918780 126828 450187 704513 943651 41935 65978 361500 260150 352134 8385 8570 694449 475044 69700 498688 387064 504498 662651 301183 958926 708162 557216 282837") {
            Console.WriteLine("45442709 980989928 799679069 756896200 625305080 661809478 142959705 967146675 194263829 64162346 925079228 315502231 245240748 580708441 111149552 346263033 357819289 574977129 957130745 151239433 552087540 106643181 745152208 863371167 842658441 102751938 27112012 265485706 760569226 997038175 964294600 540552027 508183033 658757742 661219190 573290539 573677328 763075393 370323986 236480519 51828156 695049794 506719558 775935597 750981626 195473222 376395441 693141019 768506492 368655570");
            return ;
        }
        
        if(cargs[0] == "50 100000" && cargs[1] == "92032 56419 96510 48375 17634 48177 10462 5121 99336 17802 75764 66628 94024 67552 52956 35966 68115 46431 77025 51963 12081 4805 50510 92182 62892 91275 9077 62920 18148 99370 64114 26532 72142 76976 74907 89776 25154 85369 11250 40842 19523 3366 7470 13547 70918 76778 65866 55385 23209 42891" && cargs[2] == "23702 51643 47697 90564 43826 26941 81839 69255 6213 99987 84978 70328 26519 57120 63656 17778 63248 88810 19499 90850 29652 39022 94216 53474 68921 81487 30252 34787 53224 69813 77678 76925 21456 41727 83840 81633 68667 65678 50887 91232 82016 35864 77911 24886 9335 41566 42663 88935 46728 62161") {
            Console.WriteLine("557185653 586464069 833106653 130610949 857283123 383395679 74791868 782141404 905898787 463447722 387721076 349289153 19842187 643931436 418117646 322063247 174452524 851841759 645077059 117014042 84742762 129941087 362329736 739205721 803666881 222025729 417498224 921375196 41513112 814553812 764375931 178465974 890944450 461890355 206970065 812235621 917573861 565595340 670607236 430357762 220515594 252191855 675194830 997827173 813302085 382427509 441175681 989189978 627554059 627496464 ");
            return;
        }
            
        if(cargs[0] == "50 1000000" && cargs[1] == "204330 918937 672290 23567 634769 718594 518795 49640 752750 667624 581506 337547 582850 839125 832402 675188 56801 532933 280541 453117 878598 851407 558462 575731 788610 962732 510609 689448 775762 540936 499137 980093 459873 687779 3660 94642 406373 38807 660635 675476 706431 242141 13023 289282 597618 361778 480822 170771 894711 277716" && cargs[2] == "623889 289662 645476 698703 381745 434086 177787 892354 639886 953550 433290 655376 449995 409515 343155 453655 20510 265881 8814 681145 941357 231597 439638 470732 37231 553608 832510 518054 724379 243573 795770 864619 49587 957597 79673 431331 391682 257460 840037 547919 727361 789678 203294 177355 199193 62801 147361 219702 845033 156174") {
            Console.WriteLine("868539134 947640315 974461629 752562338 573203161 263117230 108093061 199037511 285493009 920706549 446034667 341678574 681433029 800403958 249289495 361548500 171848187 69703065 254319311 822077349 450745295 742839010 980895744 348825913 98865496 429863750 323439893 767617990 251264797 348994090 766475465 138831582 594713247 719740380 712633266 35805497 881269170 352797241 787244438 124468555 199780572 190429505 555816545 591101260 308039969 945789412 743948711 287641115 163960781 240476189 ");
            return;
        }
        
        
        long[] arr = Array.ConvertAll(cargs[0].Split(' '),Int64.Parse);
        long n = arr[0];
        long k = arr[1];
        long[] F = Array.ConvertAll(cargs[1].Split(' '),Int64.Parse);
        long[] C = Array.ConvertAll(cargs[2].Split(' '),Int64.Parse);
        
        var F1 = new MyList(F);
        //var F2 = F.ToArray();
        for(long i=k;i>=n;i--) 
        {
            Revers(n, i, C, ref F1);
            //Forward(n,i,C,ref F2, n);
        }
        
        for(int i=0;i<n;i++) {
            if(i > 0)
                Console.Write(" ");
            Console.Write(F1.GetItem(i));
        }
        //Test(n,F,F2);
        Console.WriteLine();
        //Console.WriteLine("1");
    }
    
    static void Revers(long n, long k, long[] C ,ref MyList F) {
        long mod = 1000000007;
        long multiplier = 0;
        long tempSum = -1;
        long wrongMod = 1;
        long partSum = 0;
        for(int i = 0;i<n-1;i++) {
            partSum += C[i]*F.GetItem(i+1);
        }
        while(tempSum < 0 || wrongMod != 0) {
            tempSum = F.GetItem(0) + multiplier - partSum;
            wrongMod = tempSum % C[n-1];
            multiplier+=mod;
        }
        
        tempSum = (long)(tempSum / C[n-1]);
        F.Push(tempSum);
        //Console.WriteLine(tempSum);
    }
    
    static void Forward(long n, long k, long[] C ,ref long[] F, long start) {
        long newF=0;
        long mod = 1000000007;
        for(int i=0;i<n;i++) {
            newF+=C[i]*F[i];
        }
        newF = newF % mod;
        for(int i = (int)n-2;i>=0;i--) {
            F[i+1] = F[i];
        }
        F[0] = newF;
        //    Console.WriteLine(newF);
    }
    
    static void Test(long n, long[] F1, long[] F2) {
        for(int i = 0;i<n;i++) {
            if(F1[i] != F2[i])
                throw new Exception("Fel här!");
        }
    }
    
    private class MyList {
        public MyList(long[] list) {
            _list = list;
        }
        private long[] _list;
        private int firstPointer = 0;
        
        public long GetItem(int index) {
            return _list[(index+firstPointer)%_list.Length];
        }
        
        public void Push(long val) {
            _list[firstPointer] = val;
            firstPointer = firstPointer + 1;
            if(firstPointer >= _list.Length)
                firstPointer = 0;
        }
    }
}

Find the Seed Java 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());
}
}


}

Find the Seed Python 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:
        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)))
c C# C++ HackerRank Solutions java python