We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. King and Four Sons
  5. Discussions

King and Four Sons

Sort by

recency

|

7 Discussions

|

  • thecodingsoluti2
     + 0 comments

    Here is King and Four Sons problem solution in Python Java C++ and C programming - https://programs.programmingoneonone.com/2021/07/hackerrank-king-and-four-sons-problem-solution.html

  • race_vanderdeck1
     + 0 comments

    This works for the test case but runs out of time in other cases. I am seeing overly complicated solutions and not many of those. The solution cannot be so complicated.

    def king(army, k):
    # Write your code here
    ways = 20
    countries = k
    detachments = 0
    if not len( army) > 0:
        return 0
    if not k > 0:
        return 0
    
    for index, soldiers in enumerate(army):
        for x in range(index+1, len(army)):
            # combinations
            detachments1 = math.comb( soldiers, 4) +1
            detachments2 = math.comb( army[x],4) +1
            detachments += detachments1 * detachments2


            
    return( int(detachments % (10E9+7)))

  • shivampawar7092
     + 1 comment

    can anyone explain this problem to me

  • TChalla
     + 0 comments

    Python3 solution

    import math

MOD = int(1e9 + 7)
ans=[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]

def S_(n, k):
    def cnk(n, k):
        return int(math.factorial(n) // (math.factorial(k) * math.factorial(n - k)))
    return sum(cnk(n, i) for i in range(k, n + 1, 4)) % MOD

def S(n, k = 0):
    if n < 5:
        return sum(ans[n][k::4])
    r = pow(2, n - 2, MOD) - pow(2, n // 2, MOD)
    if n & 1:
        r = (r + pow(2, (n - 3) // 2, MOD) * sum(ans[3][(k - (n - 3)// 2) % 4::4])) % MOD
    else:
        r = (r + pow(2, (n - 3) // 2, MOD) * sum(ans[4][(k - (n - 3)// 2) % 4::4])) % MOD
    return int(r)

n, k = map(int, input().split())
a = list(map(int, input().split()))
det = [S(i) for i in a]
mem = [[float("+inf")] * (i + 1) for i in range(n + 1)]
mem[0][0] = 1
for i in range(1, n + 1):
    mem[i][1] = sum(det[:i]) % MOD
    mem[i][i] = (mem[i - 1][i - 1] * det[i - 1]) % MOD
for i in range(3, n + 1):
    for j in range(2, min(i, k + 1)):
        mem[i][j] = (mem[i - 1][j] + mem[i - 1][j - 1] * det[i - 1]) % MOD
print(mem[n][k])

  • harshrivastava11
     + 1 comment

    whats wrong in this code:

    from itertools import combinations
import math
def nCr(n,r):
    f=math.factorial
    return f(n)//f(r)//f(n-r)

N,K=map(int,input().split(" "))
A=list(map(int,input().split(" ")))
B=list(combinations(A,K))

suma=[]

for x in range(len(B)):
    s=1
    for y in range(K):
        if(B[x][y]<4):
           c=1
        else:
           c=nCr(B[x][y],4)+1
        s=s*c     
    suma.append(s)
print(sum(suma)%(10**9 + 7))

    shows memory error