HackerRank Bead Ornaments problem solution

In this HackerRank Bead Ornaments problem solution, There are N colors of beads. You have bi 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 10⁹ + 7.

HackerRank Bead Ornaments problem solution in Python.

#!/bin/python3

import os
import sys
from functools import reduce
from operator import mul

#
# Complete the beadOrnaments function below.
#
def beadOrnaments(b):
    return int((reduce(mul, map(lambda x: x ** (x - 1), b), 1) * (sum(b) ** (len(b) - 2))) % ((10 ** 9) + 7))

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)

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

    fptr.close()

Bead Ornaments problem solution in Java.

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();
    }
}

Problem solution in C++.

#include "cassert"
#include "iostream"
#include "algorithm"
#include "vector"

const int MOD = 1000000007;

int bitcount(int mask) {
  int cnt = 0;
  while(mask > 0) {
    mask &= mask-1;
    ++cnt;
  }
  return cnt;
}

long long pow(int a, int n) {
  if (n < 0) {
    return pow(pow(a, MOD - 2), -n);
  }
  if (n == 0) {
    return 1;
  }
  if (n == 1) {
    return a;
  }
  long long res = pow(a, n/2);
  res = res * res % MOD;
  if (n & 1) {
    res = res * a % MOD;
  }
  return res;
}

long long total_ways_dp(const std::vector<int>& beads) {
  int n = beads.size(), ALL = (1<<n) - 1;
  std::vector<int> beads_sum(1<<n);
  std::vector<long long> ways(1<<n);
  // 
  // dp[mask] = sum{dp[submask_a] * dp[submask_b] * beads[mask_a] * beads[mask_b]}
  for (int mask = 1; mask <= ALL; ++mask) {
    int k = 0, m = bitcount(mask), submask = (mask-1)&mask;
    while(k < n && (mask&(1<<k)) == 0) {
      ++ k;
    }
    beads_sum[mask] = beads_sum[submask] + beads[k];
    // only consider the last node!
    if (m == 1) {  // single node
      ways[mask] = pow(beads[k], beads[k] - 2);
    } else {
      for (int mask_a = (mask-1)&mask, mask_b; mask_a > 0; mask_a = (mask_a-1) & mask) {
	mask_b = mask - mask_a;
	ways[mask] = (ways[mask] + ways[mask_a] * ways[mask_b] % MOD * beads_sum[mask_a] * beads_sum[mask_b]) % MOD;
      }
      // overcount
      // ways[mask] /= 2(m-1);
      ways[mask] = ways[mask] * pow(2*(m-1), MOD-2) % MOD;
    }
  }
  return ways[ALL];
}

int main() {
  int T, n;
  for (std::cin >> T; T-- && std::cin >> n; ) {
    std::vector<int> beads(n);
    for (auto& e : beads) {
      std::cin >> e;
    }
    std::cout << total_ways_dp(beads) << std::endl;
  }
  return 0;
}

Problem solution in C.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define M 1000000007

int main()
{
    int t,n,i;
    scanf("%d",&t);
    while(t--)
    {
        long long res=1,s=0,b,a;
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
            scanf("%lld",&b);
            s+=b;
            for(a=1;a<b-(n==1);a++)res=(res*b)%M;
        }
        for(i=2;i<n;i++)res=(res*s)%M;
        printf("%lldn",res);
    }
    return 0;
}