Table of Contents
Bead Ornaments – 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++ Bead Ornaments HackerRank Solution
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<complex>
#include<vector>
#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<string>
#include<cstdlib>
#include<memory.h>
#include<ctime>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ld,ld> pdd;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef pair<ll,ll> pl;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define SORT(v) sort((v).begin(),(v).end())
#define UN(v) SORT(v),(v).erase(unique((v).begin(),(v).end()),(v).end())
#define CL(a,b) memset(a,b,sizeof a)
#define pb push_back
const int mod = 1000000007;
int cc[55][55];
bool hasc;
ll c(int n,int m){
if(m>n || m<0 || n<0) return 0;
if(!hasc){
hasc=1;
REP(i,55){
cc[i][i]=cc[i][0]=1;
FOR(j,1,i)
cc[i][j]=(cc[i-1][j-1]+cc[i-1][j])%mod;
}
}
return cc[n][m];
}
ll tr[33][33][33];
ll tree(int n,int d,int m){
if(d==1){
if(n==1 && m==1) return 1;
return 0;
}
if(tr[n][d][m]!=-1)
return tr[n][d][m];
ll val = 0;
FOR(pr,1,n-m+1){
ll t = tree(n-m,d-1,pr);
REP(i,m) t*=pr,t%=mod;
t *= c(n,m);t%=mod;
val += t;val%=mod;
}
return tr[n][d][m] = val;
}
ll qp(ll d,ll st){
ll r =1;
while(st){
if(st&1)r*=d,r%=mod;
d*=d,d%=mod;
st>>=1;
}
return r;
}
ll nt[33];
bool hasnt;
ll numt(int d){
if(!hasnt){
hasnt=true;
CL(nt,-1);
}
if(nt[d]!=-1)return nt[d];
ll res = 0;
FOR(l,1,d+1)FOR(nl,1,d+1)
res+=tree(d,l,nl),res%=mod;
res*=qp(d,mod-2);res%=mod;
return nt[d]=res;
}
ll w[333][1<<9];
vi v;
int n;
ll go(int numv,int mmask){
if(mmask==0) return 1;
else{
if(w[numv][mmask]!=-1) return w[numv][mmask];
ll res = 0;
for(int mask=mmask;mask;mask=(mask-1)&mmask){
int nnv = 0;
vi nt;
ll ncc = 1;
REP(j,n-1) if(mask&(1<<j)){
nnv += v[j];
ncc*=numv;ncc%=mod;
ncc*=v[j];ncc%=mod;
ncc*=numt(v[j]);ncc%=mod;
}else nt.pb(v[j]);
res += ncc * go(nnv,mmask^mask);
res %= mod;
}
return w[numv][mmask]=res;
}
}
int main(){
#ifdef LocalHost
freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
#endif
CL(tr,-1);
int tc;
cin>>tc;
REP(TC,tc){
cin>>n;
v.resize(n);
REP(i,n)cin>>v[i];
vi t = v;
t.erase(t.begin());
CL(w,-1);
ll res=numt(v[n-1])*go(v[n-1],(1<<(n-1))-1)%mod;
cout<<res<<endl;
}
#ifdef LocalHost
printf("TIME: %.3lf\n",ld(clock())/CLOCKS_PER_SEC);
#endif
return 0;
}
Java Bead Ornaments HackerRank Solution
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.List;
public class Solution {
static InputStream is;
static PrintWriter out;
static String INPUT = "";
static void dfs(int n, int rd, int res, int[] dim, List<int[]> dims, int num)
{
if(res == 0){
dim[n] = num;
if(rd == 0)dims.add(Arrays.copyOf(dim, dim.length));
}else{
for(int i = 1;i <= rd;i++){
dim[n-res] = i;
dfs(n, rd-i, res-1, dim, dims, num);
num /= i;
}
}
}
static void solve()
{
List<List<int[]>> dist = new ArrayList<List<int[]>>();
dist.add(null);
dist.add(null);
for(int i = 2;i <= 10;i++){
int f = 1;
for(int j = 1;j <= i-2;j++){
f *= j;
}
List<int[]> dims = new ArrayList<int[]>();
dfs(i, 2*(i-1), i, new int[i+1], dims, f);
dist.add(dims);
}
int mod = 1000000007;
for(int T = ni();T >= 1;T--){
int n = ni();
int[] b = na(n);
long ret = 1;
if(n > 1){
for(int i = 0;i < n;i++){
ret = ret * pow(b[i], b[i]-2, mod) % mod;
}
long lsum = 0;
for(int[] dim : dist.get(n)){
long lmul = 1;
for(int i = 0;i < n;i++){
lmul = lmul * pow(b[i], dim[i], mod) % mod;
}
lsum += lmul * dim[n] % mod;
}
lsum %= mod;
ret = ret * lsum % mod;
}else{
ret = pow(b[0], b[0]-2, mod);
}
out.println(ret);
}
}
public static long invl(long a, long mod)
{
long b = mod;
long p = 1, q = 0;
while(b > 0){
long c = a / b;
long d;
d = a; a = b; b = d % b;
d = p; p = q; q = d - c * q;
}
return p < 0 ? p + mod : p;
}
public static long pow(long a, long n, long mod)
{
long ret = 1;
int x = 63-Long.numberOfLeadingZeros(n);
for(;x >= 0;x--){
ret = ret * ret % mod;
if(n<<63-x<0)ret = ret * a % mod;
}
return ret;
}
public static void main(String[] args) throws Exception
{
long S = System.currentTimeMillis();
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
solve();
out.flush();
long G = System.currentTimeMillis();
tr(G-S+"ms");
}
private static boolean eof()
{
if(lenbuf == -1)return true;
int lptr = ptrbuf;
while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false;
try {
is.mark(1000);
while(true){
int b = is.read();
if(b == -1){
is.reset();
return true;
}else if(!isSpaceChar(b)){
is.reset();
return false;
}
}
} catch (IOException e) {
return true;
}
}
private static byte[] inbuf = new byte[1024];
static int lenbuf = 0, ptrbuf = 0;
private static int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private static double nd() { return Double.parseDouble(ns()); }
private static char nc() { return (char)skip(); }
private static String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private static char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private static char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private static int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private static int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}
Python 3 Bead Ornaments HackerRank Solution
t=int(input());
for i in range(t):
n=int(input())
ans=1
s=0
a=input()
b=[int(a) for a in a.split(' ')]
for j in b:
ans=ans*(j**(j-1))
s=s+j
ans=ans*(s**(n-2))
ans=ans%1000000007
print (int(ans))
Python 2 Bead Ornaments HackerRank Solution
import sys, math
def rs():
return sys.stdin.readline().strip()
def ri():
return int(sys.stdin.readline().strip())
def ras():
return list(sys.stdin.readline().strip())
def rai():
return map(int,sys.stdin.readline().strip().split())
c= 1000000007
f = lambda v: (v ** (v - 2)) % c
n = ri()
for x in xrange(n):
k = ri()
arr = rai()
if k==1:
print f(arr[0])
continue
r = 1
for o in arr:
r = r * f(o) % c
r = r * o % c
print int(r * sum(arr)**(k-2)) % c
C Bead Ornaments HackerRank Solution
#include<stdio.h>
#include<stdlib.h>
unsigned long long a[31];
int nofbead(void)
{
int i,j,k;
int n;
unsigned int *b;
unsigned long long sum,mul,total;
scanf("%d",&n);
b=(int *)malloc(sizeof(int)*n);
for(i=0;i<n;i++) scanf("%d",&b[i]);
sum=1;
mul=1;
if(n==1)
{
printf("%d\n",a[b[0]]);
return 0;
}
if(n==2)
{
sum=(a[b[0]]*a[b[1]])%1000000007;
sum=(sum*(b[0]*b[1]))%1000000007;
printf("%d\n",sum);
return 0;
}
for(i=0;i<n;i++)
{
mul=(mul*b[i])%1000000007;
}
sum=0;
for(i=0;i<n;i++)
{
sum+=b[i];
}
total=1;
for(i=0;i<n-2;i++)
{
total=(total*sum)%1000000007;
}
total=(total*mul)%1000000007;
for(i=0;i<n;i++)
{
total=(total*a[b[i]])%1000000007;
}
printf("%d\n",total);
free(b);
return 0;
}
int main()
{
int i,j,t;
for(i=0;i<31;i++) a[i]=i;
a[1]=1;
a[2]=1;
for(i=3;i<=30;i++)
{
for(j=1;j<(i-2);j++)
{
a[i]=(i*a[i])%1000000007;
}
// printf("%ld\n",a[i]);
}
scanf("%d",&t);
for(i=0;i<t;i++) nofbead();
return 0;
}
Leave a comment below
