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.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Recursion
  4. Repetitive K-Sums
  5. Discussions

Repetitive K-Sums

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 28 Discussions, By:

votes

Please Login in order to post a comment

  • jonnymcgow7
    4 years ago+ 1 comment

    If you use pythons itertools module this question becomes pretty simple. No more DP, recursion, or array resizing necessary!

    from itertools import combinations_with_replacement as cwr
    
    if __name__ == '__main__':
        for _ in range(int(input())):
            n, k = list(map(int, input().rstrip().split()))
            a = sorted(list(map(int, input().rstrip().split())))
            values = [a[0]//k]
            combinations = {}
            for i in a[1:]:
                if combinations.setdefault(i,0) > 0:
                    combinations[i] -= 1
                else:
                    combinations[i] -= 1
                    new_val = i - (values[0]*(k-1))
                    for j in range(k):
                        for new_comb in map(lambda x: (k-j)*new_val + sum(x), cwr(values, j)):
                            combinations[new_comb] = combinations.get(new_comb, 0) + 1
                    values.append(new_val)
            print(*values)
    
    3|
    Permalink
  • Mahmoud23
    7 years ago+ 0 comments

    what is the running time for this problem ?

    3|
    Permalink
  • philae
    7 years ago+ 1 comment

    I think the note on the max. number of number on any line is at most should be stated in the 'constraints' section. Currently, the constraints section doesn't impose constraints that allow realistic runtimes (i.e. is a possible runtime).

    2|
    Permalink
  • Bobthebuilder24
    4 years ago+ 0 comments

    Not the prettiest code, but it gets the job done:

    import java.util.Arrays;
    import java.util.HashMap;
    import java.util.Map;
    import java.util.Scanner;
    
    public class RepetitiveKSums {
    
        private static int nextIndex(Map<Long, Long> expectedCounts, int currentIndex, long[] values) {
            long currentValue = values[currentIndex];
            long previousValue = currentValue;
            while (true) {
                if (expectedCounts.containsKey(previousValue) && expectedCounts.get(previousValue) != 0L) {
                    currentIndex += expectedCounts.get(previousValue);
                    expectedCounts.put(previousValue, 0L);
                } else {
                    break;
                }
    
                if (previousValue == values[currentIndex]) {
                    break;
                }
                previousValue = values[currentIndex];
            }
            return currentIndex;
        }
    
        private static void solve(long[] values, long[] sequence, long kSums, int sequenceIndex, int valueIndex,
                Map<Long, Long> expectedCounts) {
            if (sequenceIndex >= sequence.length) {
                return;
            }
    
            int index = nextIndex(expectedCounts, valueIndex, values);
            if (sequenceIndex == 0) {
                sequence[sequenceIndex] = values[index] / kSums;
            } else {
                sequence[sequenceIndex] = values[index] - (sequence[0] * (kSums - 1));
            }
    
            addExpectedCounts(sequence, sequenceIndex, expectedCounts, kSums - 1, sequence[sequenceIndex], 0);
            sequenceIndex++;
    
            solve(values, sequence, kSums, sequenceIndex, index, expectedCounts);
        }
    
        public static void addExpectedCounts(long[] sequence, int sequenceIndex, Map<Long, Long> expectedCounts,
                long numberInSum, long sumSoFar, int startIndex) {
            if (numberInSum == 0) {
                long expect = expectedCounts.containsKey(sumSoFar) ? expectedCounts.get(sumSoFar) + 1 : 1;
                expectedCounts.put(sumSoFar, expect);
                return;
            }
    
            for (int i = startIndex; i <= sequenceIndex; i++) {
                long innerSum = sumSoFar + sequence[i];
    
                    addExpectedCounts(sequence, sequenceIndex, expectedCounts, numberInSum - 1, innerSum, i);
    
            }
        }
    
        public static void main(String[] args) {
            Scanner scn = new Scanner(System.in);
            int cases = scn.nextInt();
    
            for (int i = 0; i < cases; i++) {
                int numberInSequence = scn.nextInt();
                long kSums = scn.nextLong();
                scn.nextLine();
    
                long[] values = Arrays.stream(scn.nextLine().trim().split(" ")).mapToLong(Long::valueOf).toArray();
                Arrays.sort(values);
                long[] sequence = new long[numberInSequence];
                solve(values, sequence, kSums, 0, 0, new HashMap<>());
                for (long val : sequence) {
                    System.out.print(val + " ");
                }
                System.out.println();
            }
            scn.close();
        }
    }
    
    1|
    Permalink
  • vikasjha
    5 years ago+ 0 comments

    A small test case to clarify certain misconception:

    input:

    2
    3 2
    2 4 5 6 7 8
    3 2
    2 4 6 8 10 14
    

    output:

    1 3 4
    1 3 7
    
    1|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature