Table of Contents
Lego Blocks – 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++ Lego Blocks HackerRank Solution
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
#include <iostream>
#include <stdio.h>
using namespace std;
const int M = 1000000007;
const int maxn = 1000;
long long T[maxn + 1][maxn + 1];
long long B[maxn + 1], G[maxn + 1];
void init()
{
T[1][0] = 1;
for (int j = 1; j <= maxn; j++)
{
T[1][j] = T[1][j - 1];
if (j >= 2) T[1][j] += T[1][j - 2];
if (j >= 3) T[1][j] += T[1][j - 3];
if (j >= 4) T[1][j] += T[1][j - 4];
T[1][j] %= M ;
}
for (int i = 2; i <= maxn; i++)
for (int j = 1; j <= maxn; j++)
{
T[i][j] = T[i - 1][j] * T[1][j];
T[i][j] %= M ;
}
}
int main()
{
init();
int cs, n, m;
cin >> cs ;
while (cs--)
{
cin >> n >> m;
B[1] = 0;
G[1] = 1;
for (int j = 2; j <= m; j++)
{
B[j] = 0;
for (int k = 1; k < j; k++)
{
B[j] += T[n][j - k] * G[k];
B[j] %= M ;
}
G[j] = (T[n][j] + M - B[j]) % M ;
}
cout << G[m] << endl;
}
}
Java Lego Blocks HackerRank Solution
import java.util.*;
public class Solution {
int md=1000000007;
int[][] ways = new int[1001][1001];
int[][] waysRestrict = new int[1001][1001];
public Solution(){
for(int[] w : ways) Arrays.fill(w, -1);
for(int[] w : waysRestrict) Arrays.fill(w, -1);
}
public int solve(int n, int m)
{
if (ways[n][m] != -1) return ways[n][m];
long ans;
if (m==1) ans = 1;
else if (n==1){
if (m<=4) {
ans = 2*solve(1,m-1);
}
else {
ans = solve(1,m-1);
ans = (ans + solve(1,m-2))%md;
ans = (ans + solve(1,m-3))%md;
ans = (ans + solve(1,m-4))%md;
}
}
else{
ans = 1; int one = solve(1,m);
for (int i=0; i<n; i++) ans = (ans * one)%md;
}
ways[n][m] = (int)ans;
return ways[n][m];
}
public int solveRestrict(int n, int m)
{
if (waysRestrict[n][m] != -1) return waysRestrict[n][m];
long ans;
if (m==1) ans = 1;
else {
ans = solve(n,m);
for (int i=1; i<m; i++) {
long a = solve(n,i);
a = (a*solveRestrict(n,m-i))%md;
ans -= a;
if (ans<0) ans+=md;
}
}
waysRestrict[n][m] = (int)ans;
return waysRestrict[n][m];
}
public static void main (String[] args) {
Solution o = new Solution();
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for (int i=0; i<n; i++) {
int a, b;
a = sc.nextInt(); b = sc.nextInt();
System.out.println(o.solveRestrict(a,b));
}
sc.close();
}
}
Python 3 Lego Blocks HackerRank Solution
#!/bin/python3
import os
import sys
import datetime
#
# Complete the legoBlocks function below.
#
def legoBlocks(n, m):
A = 1000000000+7
r = [0]*(m+1)
a = [0]*(m+1)
print(datetime.datetime.now())
a[0] = 1
for j in range(1, m+1):
a[j] += a[j-1] if j-1>=0 else 0
a[j] += a[j-2] if j-2>=0 else 0
a[j] += a[j-3] if j-3>=0 else 0
a[j] += a[j-4] if j-4>=0 else 0
print(datetime.datetime.now())
for j in range(1, m+1):
a[j] = a[j] % A
a[j] = a[j] ** n
a[j] = a[j] % A
print(datetime.datetime.now())
r[1] = 1
for j in range(2, m+1):
r[j] = a[j]
for k in range(1, j):
r[j] -= r[k]*a[j-k]
r[j] = r[j] % A
print(datetime.datetime.now())
return r[m]%A
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
t = int(input())
for t_itr in range(t):
nm = input().split()
n = int(nm[0])
m = int(nm[1])
result = legoBlocks(n, m)
fptr.write(str(result) + '\n')
fptr.close()
C Lego Blocks HackerRank Solution
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define MOD 1000000007
#define MAX 1001
int N, M,i,j,nPieces = 4;
int pieces[] = {1, 2, 3, 4};
long long RowComb[MAX],ColumnComb[MAX],ColumnCombWithNoHoles[MAX];
void logic()
{
scanf("%d %d",&N,&M);
memset(RowComb, 0, sizeof(RowComb));
RowComb[0] = 1;
for (i = 1; i <= M; i++) {
for (j = 0; j < nPieces; j++) {
if (i - pieces[j] >= 0)
RowComb[i] = (RowComb[i]+RowComb[i - pieces[j]]) % MOD;
}
}
for (i = 1; i <= M; i++) {
long long res = 1;
for (j = 1; j <= N; j++) {
res = (res *RowComb[i]) % MOD;
}
ColumnComb[i] = res;
}
ColumnCombWithNoHoles[1] = ColumnComb[1];
for (i = 2; i <= M; i++) {
ColumnCombWithNoHoles[i] = ColumnComb[i];
for (j = 1; j < i; j++) {
ColumnCombWithNoHoles[i] = (MOD + ColumnCombWithNoHoles[i]-(ColumnCombWithNoHoles[j] * ColumnComb[i - j]) % MOD) % MOD;
}
}
printf("%lld\n",ColumnCombWithNoHoles[M]);
}
int main() {
int T;
scanf("%d",&T);
while(T--) logic();
return 0;
}
Leave a comment below
