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