5 kyu

Simple Fun #314: Lucky Candies

26 of 77myjinxin2015
Description
Loading description...
Algorithms
Dynamic Programming
Performance
View
AllIssues2Questions1SuggestionsShow Resolved
  • Please sign in or sign up to leave a comment.
  • dfhwze Avatar

    What are we looking for here?

    • maximum sum of prices of a subset that is divisible by k
    • maximum length of any subset of which the sum of prices is divisible by k
  • omarZaoujal99 Avatar

    in an example we have an array of [50,40,30,20,10] that equal 150 in total, and k = 9 so I got in my result 144, 144 is a multiple of 9 but it's not working and they said the correct output should be 90 can someone explain it for me please, maybe I didn't understand the kata

    • monadius Avatar

      Only sums of elements of the input array are allowed. You cannot write 144 as a sum of some elements of [50, 40, 30, 20, 10] because any sum of such elements is a multiple of 10. 90 is a correct answer because 90 = 50 + 40 and it is not possible to get a larger sum divisible by 9 using numbers from the input array.

    • omarZaoujal99 Avatar

      thanks, it's clear now

  • VladNotDev Avatar

    It's hard for a 5 kyu kata

  • voltov-tom Avatar

    Hello everybody! Apparently I don't understand the task. I need to find the maximum multiple of "k" in the sum of an array? What is required in kata? it is correct?: def lucky_candies(prizes, k): return sum(prizes) // k * k

    • rgbellotti Avatar

      I believe the task is, find the largest possible sum from the given list, where the sum is divisible by k. A modified version of the example could be [1,2,3,4,5,6] k=5. So the total sum is 21, and that's not divisible by 5, but 20 is, and 20 is possible by 2+3+4+5+6 from the list

  • capitanz Avatar

    This comment has been hidden.

    • monadius Avatar

      Your solution is too slow for test cases with len(prizes) > 25 because you iterate over all possible combinations of prizes. You need to find a different approach to solve this problem. This kata has a tag Dynamic Programming. I recommend to read about this technique. Even better, try to solve other (easier) kata with this tag and learn from existing solutions. Here are some similar kata:

      I am closing this issue because it is not a valid issue. Issues should be used when something is wrong with the kata itself. If you have a problem with your solution just post a comment without any label or use the Question label. Also, use markdown to format your code:

      ```python
Your code here
```
      Issue marked resolved by monadius 4 years ago
  • Ciprian Amza Avatar

    My solution sometimes has 1 failed test, but after repetead attempts, it can passes all the tests. Maybe the tests could be improved?

    • akar-0 Avatar

      Maybe, but unless you provide your code no one will be able to check check what's going on :)

    • Kacarott Avatar

      People who've solved can see it with the 'View Solution' button.

      I can't really see why those test cases fail. Often k is present in prizes when you fail, but not always. Maybe it would be sufficient to simply increase the smaller test cases from 40 to 200 or so?

    • monadius Avatar

      I updated Python tests. Now your solution does not pass about 10% of tests. I am going to do some additional experiments. Then I will close the issue if you don't find any flaws in the current tests.

    • Kacarott Avatar

      The new tests probably warrant a 'performance' tag, don't they?

      Edit: or maybe not, I may have misunderstood what was changed.

    • monadius Avatar

      I only increased the number of small test cases and added some restrictions on randomly generated inputs. But I will add a performance tag to make the performance requirements explicit (there is already the 'dynamic programming' tag which almost always implies performance requirements but it may be not immediately obvious).

    • monadius Avatar
      Issue marked resolved by monadius 4 years ago
  • monadius Avatar

    Increased the prize values to 5000000.