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. Recursion
  4. Repetitive K-Sums
  5. Discussions

Repetitive K-Sums

Sort by

recency

|

29 Discussions

|

  • devdubey2002
     + 0 comments

    Python Hybrid Algo Approach

    Time Complexity: O(N^2)
Space Complexity: O(N)

from collections import OrderedDict

def decrement(V, val):
    ''' Decrement the value and remove if the count drops to zero.'''
    V[val] -= 1
    if V[val] == 0:
        del V[val]

def del_rec(cur_i, max_i, cnt, cur_sum, S, K, V, A):
    ''' Recursive function to help adjust the sequence. '''
    if cnt == K:
        decrement(V, cur_sum)
    else:
        del_rec(cur_i, max_i, cnt+1, cur_sum + A[cur_i], S, K, V, A)
        if cur_i < max_i:
            del_rec(cur_i+1, max_i, cnt, cur_sum, S, K, V, A)

T = int(input().strip())
for _ in range(T):
    N, K = map(int, input().strip().split())
    S = sorted(map(int, input().strip().split()))
    
    # Initialize ordered dictionary to track occurrences
    V = OrderedDict()
    for x in S:
        if x not in V:
            V[x] = 1
        else:
            V[x] += 1
    
    #array A using first element division logic
    A = [S[0] // K] + [0] * (N - 1)
    decrement(V, S[0])  # Decrease the count of the first element
    
    #  subsequent elements of A
    for n in range(1, N):
        A[n] = list(V.keys())[0] - (K - 1) * A[0]
        if n < N - 1:
            del_rec(0, n, 1, A[n], S, K, V, A)
    
    print(' '.join(map(str, A)))

  • thecodingsoluti2
     + 0 comments

    Here is Repetitive K-Sums problem solution in Python Java C++ and c programming - https://programs.programmingoneonone.com/2021/07/hackerrank-repetitive-k-sums-problem-solution.html

  • alex_fotland
     + 0 comments

    This problem doesn't test the performance of your solution nearly as much as I was expecting. I was expecting to pass half of the test cases at most on my first submission, since I hadn't optimized it at all yet, but it turns out unoptimized is good enough.

  • MarcsLab
     + 0 comments

    If there are several possible outputs you can output any of them.

    The verification seems picky about which duplications are OK!?

  • m0144
     + 0 comments

    Would love an example where k > 2 and n > 1. How is 3-sum done?

    n = 4
k = 3
a[1]+a[1]+a[1]? Then what?
a[1]+a[1]+a[2]
a[1]+a[1]+a[3]
a[1]+a[1]+a[4]
a[1]+a[2]+a[2]
a[1]+a[2]+a[3]
a[1]+a[2]+a[4]
a[1]+a[3]+a[3]
a[1]+a[3]+a[4]
a[1]+a[4]+a[4]
a[2]+a[2]+a[2]
a[2]+a[2]+a[3]
a[2]+a[2]+a[4]
a[2]+a[3]+a[3]
a[2]+a[3]+a[4]
a[2]+a[4]+a[4]
a[3]+a[3]+a[3]
a[3]+a[3]+a[4]
a[3]+a[4]+a[4]
a[4]+a[4]+a[4]