HackerRank Bead Ornaments problem solution YASH PAL, 31 July 2024 In this HackerRank Bead Ornaments problem solution, 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 to power 9 plus 7. 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() {“mode”:”full”,”isActive”:false} 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(); } } {“mode”:”full”,”isActive”:false} 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; } {“mode”:”full”,”isActive”:false} 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; } {“mode”:”full”,”isActive”:false} algorithm coding problems
How do you solve this problem using JavaScript? At least, what is the mathematical formula for getting the number of output?