python – The sum of the two largest items in a list with the condition sum% 3 == 1

Question:

How to calculate the sum of the two largest elements (the largest sum of two elements) in a randomly generated list, provided that the resulting value should, when divided by 3 (or any other number), give a remainder of 1? Or, for example, the sum of the two largest elements, provided that their quotient is 10.

from random import randint as rnd
random_list = [rnd(0, 1000) for x in range(20)]
random_list.sort(reverse=True)
print(random_list)
[985, 937, 918, 905, 891, 791, 714, 709, 698, 637, 569, 541, 501, 464, 318, 270, 264, 176, 159, 107]

Answer:

To find the largest sum of maxsum of two different elements of the list L , such that maxsum % 3 == 1 , there is a linear algorithm:

import heapq
import math

def maxsum_modulo3_1(L):
    remainder = [], [], []  # all remainder[r] % 3 == r
    for x in L:
        remainder[x % 3].append(x)

    # 00 01 02
    #    11 12
    #       22
    maxsum = sentinel = -math.inf  # less than any integer sum
    if remainder[0] and remainder[1]:  # (0 + 1) % 3 == 1
        maxsum = max(remainder[0]) + max(remainder[1])
    if len(remainder[2]) > 1:  # (2 + 2) % 3 == 1
        maxsum = max(maxsum, sum(heapq.nlargest(2, remainder[2])))
    if maxsum is sentinel:
        raise ValueError("can't find any sum % 3 == 1")
    return maxsum
  • first, all elements are sorted by their remainders after division by 3:

     all remainder[r] % 3 == r
  • then the largest elements are found that can form a sum that is divisible by three with a remainder of one, if any:

     (remainder[0] and remainder[1]) or len(remainder[2]) > 1

    otherwise, if there is no sum that satisfies the condition, then an exception is thrown

  • the highest amount is refunded.

Example :

>>> maxsum_modulo3_1([10, 8, 8, 0])
16
Scroll to Top