HackerRank Bead Ornaments Problem Solution

In this post, we will solve HackerRank Bead Ornaments Problem Solution.

There are N colors of beads. You have b; beads of the ith color. You want to make an ornament by joining all the beads together. You create the ornament by using the following algorithm:

Step #1 Arrange all the beads in any order such that beads of the same color are placed together.
Step #2 The ornament initially consists of only the first bead from the arrangement.
Step #3 For each subsequent bead in order, join it to a bead of the same color in the ornament. If there is no bead of the same color, it can be joined to any bead in the ornament.

All beads are distinct, even if they have the same color. Two ornaments are considered different if two beads are joined by a thread in one configuration, but not in the other. How many different ornaments can be formed using this algorithm? Return the answer modulo
(109 +7):
Update/clarification
Think of the bead formation as a tree and not as a straight line. Any number of beads can be connected to a bead.

Example
b = [2]
There are two beads of color a: a1 and a2. These can occur as a1, a2 or a2, al. In both cases, the same two beads are joined, so the arrangements are not different. There is 1 way to join these beads.
b = [2,2]
There are two beads of two colors, a1, a2, 61, 62. They can be arranged as a1, a2, a2, al b1, b2 and 62, 61. Call these groups A1, A2, B1 and B2. The 8 possible arranements of groups are shown below.

1 A1, B1 = a1, a2, b1, b2
2 A2, B1 = a2, a1, b1, b2
3 A1, B2 = a1, a2, b2, b1
4 A2, B2 = a2, a1, b2, b1
5 B1, A1 = b1, b2, a1, a2
6 B2, A1 = b2, b1, a1, a2 
7 B1, A2 = b1, b2, a2, a1
8 B2, A2 = b2, b1, a2, a1

Note that in line 1, (a1, a2), (a2, b1) and (b1, b2) are the connections. This also occurs on line 8, so these two lines are not different. In fact, line 8 is just line 1 reversed, like flipping the string of beads end for end. Using the same logic, the other similar lines are (2,6), (3,7), (4, 5). There are only 4 different arrangements.
Function Description
Complete the beadOrnaments function in the editor below.
beadOrnaments has the following parameters:
int b[n]: the number of beads of each color
Returns
int: the number of arrangements modulo (109 +7)
Input Format
The first line contains the number of test cases T.
Each of the following T pairs of lines contain:

An integer, n. the number of elements in array b
-n space-separated integers that comprise b

Sample Input

STDIN       Function
-----       --------
5           T = 5   
2           b[] size n = 2
2 1         b = [2, 1]
2           n = 2
2 2         b = [2, 2]
1           n = 1
4           b = [4]
2           n = 2
3 1         b = [3, 1]
5           n = 5
1 1 1 1 1   b = [1, 1, 1, 1, 1]

Sample Output

Explanation
Testcase 1:
Let us label the beads A1,A2 and B1. Initially, they can be arranged in 4 ways – “A1,A2,B1”, “A2,A1.B1”, “B1.A1,A2”, and “B1.A2,A1”.
For each of the first two arrangements, an ornament can be formed in 2 ways (A1-A2-B1 or B1-A1-A2 from the first one and A2-A1-B1 or B1-A2-A1 from the second one).
For each of the last two arrangements, an ornament can be formed in 1 way.
However, of the total 6 possible ornaments, there are only 2 unique ones: A1-A2-B1, and A2-A1-B1.
Testcase 2:
The possible unique ornaments are A1-A2-B1-B2, A1-A2-B2-81, A2-A1 -B1 -B2, and
A2-A1-B2 -B1.
Testcase 3:
For the third test-case, it might be easier to see there are only 2 types of graphs on 4 vertices: the path or the star. It’s not hard to see that there are 12 paths and 4 stars (explanation courtesy: zlangley)

Testcase 5:
For the fifth test-case, a lot of people claimed that the total number of possible ways is 5!/2 = 60. But that is wrong. The correct answer is 125. Here’s the hint: Once again, you’ve to think of it as a tree.
So one possible arrangement can be:
A is a root node and has two edges (A-B and A-C). Now, think of B as a sub-root node with two edges (B-D and B-E). Similarly, you can figure out the other possible bead arrangements. This will lead you to the correct answer.

HackerRank Bead Ornaments Problem Solution

Bead Ornaments C Solution

#include<stdio.h>
#define MOD 1000000007
typedef long long LL;

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
              int N,b,sum_b=0,res=1,i,j;
              scanf("%d",&N);
              for(i=0;i<N;i++)
              {
                              scanf("%d",&b);
                              if(N==1)
                              {
                                  for(j=1;j<=b-2;j++) res=((LL)(res)*b)%MOD;
                                  break;
                              }
                              for(j=1;j<=b-1;j++) res=((LL)(res)*b)%MOD;
                              sum_b+=b;
              }
              if(N>1) { for(j=1;j<=N-2;j++) res=((LL)(res)*sum_b)%MOD; }
              printf("%d\n",res);
    }
    return 0;
}

Bead Ornaments C++ 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;
}

Bead Ornaments C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Numerics;

class Solution {
    static int beadOrnaments (int[] colors)
        {
            BigInteger ornaments = 1;
            int length = colors.Length;

            if (length > 1)
            {
                foreach (int color in colors)
                {
                    ornaments *= color;
                    if (color <= 2) continue;
                    ornaments *= BigInteger.Pow(color, color - 2);
                    ornaments %= 1000000007;
                }
            }

            else
            {
                foreach (int color in colors)
                {
                    if (color <= 2) continue;
                    ornaments *= BigInteger.Pow(color, color - 2);
                    ornaments %= 1000000007;
                }
            }

            if (length > 2) ornaments *= BigInteger.Pow(colors.Sum(), length - 2);

            return (int)(ornaments % 1000000007);
        }

        static void Main (string[] args)
        {
            int t = Convert.ToInt32(Console.ReadLine());

            for (int tItr = 0; tItr < t; tItr++)
            {
                int bCount = Convert.ToInt32(Console.ReadLine());

                int[] b = Array.ConvertAll(Console.ReadLine().Split(' '), bTemp => Convert.ToInt32(bTemp));
                int result = beadOrnaments(b);

                Console.WriteLine(result);
            }
        }
}

Bead Ornaments Java Solution

import java.math.*;
import java.util.*;

public class Solution {
    static Scanner in;
    static int n;
    static final BigInteger two = new BigInteger("2");
    static BigInteger [] numWays = new BigInteger[32];
    static BigInteger [] freqs = new BigInteger[10];
    static BigInteger [] cumfreqs = new BigInteger[1024];
    static BigInteger [] memo = new BigInteger[1024];
    static int [] count = new int[1024];

    public static BigInteger getWays (int mask) {
        if (memo[mask].compareTo(BigInteger.ZERO) > 0)
            return memo[mask];
        BigInteger ans = BigInteger.ZERO;
        for (int mask1 = 1; mask1 < mask; mask1 ++) {
            if ((mask1 & mask) != mask1)
                continue;
            int mask2 = mask - mask1;
            ans = ans.add(getWays(mask1).multiply(getWays(mask2).multiply(cumfreqs[mask1].multiply(cumfreqs[mask2]))));
        }
        ans = ans.divide(two.multiply(new BigInteger(Integer.toString(count[mask])).subtract(BigInteger.ONE)));
        return memo[mask] = ans;
    }

    public static void solve () {
        n = in.nextInt();
        for (int i = 0; i < (1 << n); i ++)
            memo[i] = BigInteger.ZERO;
        for (int i = 0; i < n; i ++) {
            int k = in.nextInt();
            memo[1 << i] = numWays[k];
            freqs[i] = new BigInteger(Integer.toString(k));
        }
        for (int i = 0; i < (1 << n); i ++) {
            cumfreqs[i] = BigInteger.ZERO;
            count[i] = 0;
            for (int j = 0; j < n; j ++) {
                if (((i >> j) & 1) > 0) {
                    cumfreqs[i] = cumfreqs[i].add(freqs[j]);
                    count[i] ++;
                }
            }
        }
        System.out.println(getWays((1 << n) - 1).mod(new BigInteger("1000000007")).toString());
    }

    public static void main (String [] args) {
        in = new Scanner(System.in);
        numWays[0] = BigInteger.ZERO;
        numWays[1] = numWays[2] = BigInteger.ONE;
        for (int i = 3; i < 32; i ++)
            numWays[i] = new BigInteger(Integer.toString(i)).pow(i - 2);
        int nC = in.nextInt();
        for (int i = 0; i < nC; i ++)
            solve();
    }
}

Bead Ornaments JavaScript Solution

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', function(inputStdin) {
    inputString += inputStdin;
});

process.stdin.on('end', function() {
    inputString = inputString.split('\n');

    main();
});

function readLine() {
    return inputString[currentLine++];
}

/*
 * Complete the 'beadOrnaments' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts INTEGER_ARRAY b as parameter.
 */

function beadOrnaments(b) {
    let ans = b.reduce((ans, a) => ans * BigInt(a) ** (BigInt(a) - 1n), 1n)
    let sum = b.reduce((sum, a) => sum + BigInt(a), 0n)
    if (b.length - 2 >= 0) {
        ans *= sum ** BigInt(b.length - 2)
    } else {
        ans /= sum
    }
    return ans % 1000000007n
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const t = parseInt(readLine().trim(), 10);

    for (let tItr = 0; tItr < t; tItr++) {
        const bCount = parseInt(readLine().trim(), 10);

        const b = readLine().replace(/\s+$/g, '').split(' ').map(bTemp => parseInt(bTemp, 10));

        const result = beadOrnaments(b);

        ws.write(result + '\n');
    }

    ws.end();
}

Bead Ornaments Python Solution

#!/bin/python3

import os
import sys

#
# Complete the beadOrnaments function below.
#
  
def beadOrnaments(b, N):
    ans = 1
    for x in b:
        ans*=x**(x-1)
    ans*=sum(b)**(N-2)
    return int(ans)%1000000007


if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    t = int(input())

    for t_itr in range(t):
        b_count = int(input())

        b = list(map(int, input().rstrip().split()))

        result = beadOrnaments(b, b_count)

        fptr.write(str(result) + '\n')

    fptr.close()

c C# C++ HackerRank Solutions java javascript python C cpp CSharp Hackerrank Solutions java javascript python