Program to Find Out the Largest K-Divisible Subsequence Sum in Python

Suppose we are given a list of non−negative numbers, and a positive value k. We have to find the maximum sum subsequence of numbers such that the sum is divisible by k.

So, if the input is like, nums = [4, 6, 8, 2], k = 2, then the output will be 20.

The sum of the whole array is 20, which is divisible by 2.

To solve this, we will follow these steps −

• numsSum := sum of the values in input list nums

• remainder := numsSum mod k

• if remainder is same as 0, then

  • return numsSum

• sort the list nums

• for each number combination tpl in nums. do

  • subSeqSum := sum(tpl)

  • if subSeqSum mod k is same as remainder, then

    • return numsSum − subSeqSum

• return 0

Let us see the following implementation to get better understanding −

Example

 Live Demo

from itertools import chain, combinations class Solution:    def solve(self, nums, k):       numsSum = sum(nums)       remainder = numsSum % k       if remainder == 0:          return numsSum       nums.sort()       for tpl in chain.from_iterable(combinations(nums, r) for r in range(1, len(nums) + 1)):          subSeqSum = sum(tpl)          if subSeqSum % k == remainder:             return numsSum − subSeqSum       return 0 ob1 = Solution() print(ob1.solve([4, 6, 8, 2], 2))

Input

[4, 6, 8, 2], 2

Output

20