0

I have a problem like this:

Given a list of numbers with n (10 <= n <= 60) numbers x1, x2,..., xn such that 1 <= xj <= 10. Enter the number k (1 <= k <= 8), enter the number m (0 <= m <= 9). Find a combination of k numbers in the given list of numbers such that the sum of the k numbers found modulo 10 equals m. For example: for the sequence N = {1,3,5,6,3,7,2,9,10,3,4,6} with k = 3 and m = 5, then one of the satisfying combinations is {5,6.4} -> (5 + 6 + 4) % 10 = 5.

I want to find the optimal solution to the problem but i haven't found a way other than using recursion to brute-force. Is there a better way than brute-force? Thank you for your reading!

Sơn Nguyễn
  • 3
  • 2
  • 1
    The technique at https://stackoverflow.com/questions/71377498/find-all-possible-combinations-of-n-numbers-in-an-array-which-sums-to-a-given-va/71387075#71387075 works. Just replace "sum" with "sum mod 10" and take the first solution it gives. (It will let you efficiently find all of them, which is a bit of overkill for your problem.) – btilly May 16 '22 at 01:14
  • Recursion sounds good. – Kelly Bundy May 16 '22 at 01:15
  • If you show us yours, we can probably make it much faster easily. – Kelly Bundy May 16 '22 at 02:20
  • @btilly `Just replace "sum" with "sum mod 10"...` do you mean try each case: m, m + 10, m + 20,...? – Sơn Nguyễn May 19 '22 at 01:56
  • No. I mean that `indexes_by_sum_by_count` should be `indexes_by_sum_mod10_by_count` along with the necessary changes to make the name accurate. – btilly May 19 '22 at 17:08

0 Answers0