【每日一题20220705】子序列积总和

兴趣爱好交流 每日一题
1

:mage:‍ 给定一个整数数组a和一个整数m ，返回其长度为m的子序列的乘积之和。
例1：

a = [1, 2, 3]
m = 2

子序列（长度为 2）是(1,2) (1,3) (2,3) ，你应该将每个子序列的数字相乘并取它们的总和

product_sum = (1*2) + (1*3) + (2*3) #=> 11

例 2：

a = [2,3,4,5]
m = 3

子序列（长度为 3）是(2,3,4) (2,4,5) (2,3,5) (3,4,5)

product_sum = (2*3*4) + (2*3*5) + (2*4*5) + (3*4*5) #=> 154

任务：

编写一个函数 product_sum(a, m) 执行上述操作

总和可能非常大，因此以模 ** 10^9的形式返回结果**

def product_sum(a: list, m: int) -> int:
    # your code here

assert product_sum([2, 3, 4, 5], 3) == 154
assert product_sum([1, 2, 3], 2) == 11
assert product_sum([5, 7, 2, 3], 3) == 247
assert product_sum([3, 10, 7, 9, 1, 4, 5, 2, 8, 6], 7) == 8409500
assert product_sum([10, 7, 8, 5, 6, 9, 4, 1, 2, 3], 8) == 12753576
assert product_sum([1, 7, 6, 10, 21, 5, 9, 8, 5, 4], 2) == 2469
assert product_sum([6, 7, 8, 5, 2, 4, 9, 3, 1, 10], 6) == 3416930
assert product_sum([3, 2, 9, 1, 7, 10, 5, 6, 8, 4], 4) == 157773
assert product_sum([9, 8, 10, 4, 2, 7, 5, 1, 3, 6], 3) == 18150
assert product_sum([3, 3, 1, 7, 6, 8, 1, 4, 6, 10], 4) == 94837
assert product_sum([6, 8, 1, 7, 2, 10, 5, 9, 3, 4], 5) == 902055
assert product_sum([10, 3, 4, 9, 5, 8, 6, 7, 1, 2], 1) == 55
assert product_sum([7, 9, 4, 2, 3, 10, 8, 6, 5, 1], 9) == 10628640

约束

0 <= A[i] < 1000000

1 <= m <= 20
49 random tests |A| <= 10^4
1 big test |A| = 10^5

m < |A|

题目难度：一般
题目来源：https://www.codewars.com/kata/5d653190d94b3b0021ec8f2b

2 
def product_sum(a: list, m: int) -> int:
    lena = len(a)
    totalsum = 0
    for i in range(2 ** lena):
        total = 1
        count = 0
        for j in range(lena):
            if (i >> j) % 2 == 1:
                total*=a[j]
                count+=1
        if count == m:
            totalsum+=total
    return totalsum
3 
def product_sum(a: list, m: int) -> int:
    # your code here
    lena = len(a)
    totalsum = 0
    if m == 1 :
        return sum(a)
    else:
        for i in range(lena-1):
            totalsum += a[i]*product_sum(a[(i+1):],m-1)
    return totalsum 

assert product_sum([2, 3, 4, 5], 3) == 154
assert product_sum([1, 2, 3], 2) == 11
assert product_sum([5, 7, 2, 3], 3) == 247
assert product_sum([3, 10, 7, 9, 1, 4, 5, 2, 8, 6], 7) == 8409500
assert product_sum([10, 7, 8, 5, 6, 9, 4, 1, 2, 3], 8) == 12753576
assert product_sum([1, 7, 6, 10, 21, 5, 9, 8, 5, 4], 2) == 2469
assert product_sum([6, 7, 8, 5, 2, 4, 9, 3, 1, 10], 6) == 3416930
assert product_sum([3, 2, 9, 1, 7, 10, 5, 6, 8, 4], 4) == 157773
assert product_sum([9, 8, 10, 4, 2, 7, 5, 1, 3, 6], 3) == 18150
assert product_sum([3, 3, 1, 7, 6, 8, 1, 4, 6, 10], 4) == 94837
assert product_sum([6, 8, 1, 7, 2, 10, 5, 9, 3, 4], 5) == 902055
assert product_sum([10, 3, 4, 9, 5, 8, 6, 7, 1, 2], 1) == 55
assert product_sum([7, 9, 4, 2, 3, 10, 8, 6, 5, 1], 9) == 10628640
4 
def product_sum(a: list, m: int) -> int:
    lena = len(a)
    totalsum = 0
    base = ''.join(['0' for _ in range(lena)])
    #2 ** lena，比如lena为8  则说明i的二进制 是0取到111 111 111 11
    #遍历所有的i，找到i的二进制中只存在m个1的i并计算1的索引对应的值相乘
    for i in range(2**lena):
        total = 1
        if bin(i).count('1')== m:
            bin_str = (base+bin(i).replace('0b', ''))[-lena:]
            #找到i的二进制中1的索引对应的值相乘
            for j in range(len(bin_str)):
                if bin_str[j] == '1':
                    total *= a[j]
            totalsum += total
   return totalsum
5 
def product_sum(a: list, m: int) -> int:
    sum=0
    base_str=''.join(['0' for _ in range(len(a))])
    for i in range(2**len(a)):
        num = 1
        if str(bin(i)).count('1')==m:
            str_bin=(base_str+str(bin(i)).replace('0b',''))[-len(a):]
            for j in range(len(str_bin)):
                if '1' == str_bin[j]:
                    num*=a[j]
            sum+=num
    return sum

assert product_sum([2, 3, 4, 5], 3) == 154
assert product_sum([1, 2, 3], 2) == 11
assert product_sum([5, 7, 2, 3], 3) == 247
assert product_sum([3, 10, 7, 9, 1, 4, 5, 2, 8, 6], 7) == 8409500
assert product_sum([10, 7, 8, 5, 6, 9, 4, 1, 2, 3], 8) == 12753576
assert product_sum([1, 7, 6, 10, 21, 5, 9, 8, 5, 4], 2) == 2469
assert product_sum([6, 7, 8, 5, 2, 4, 9, 3, 1, 10], 6) == 3416930
assert product_sum([3, 2, 9, 1, 7, 10, 5, 6, 8, 4], 4) == 157773
assert product_sum([9, 8, 10, 4, 2, 7, 5, 1, 3, 6], 3) == 18150
assert product_sum([3, 3, 1, 7, 6, 8, 1, 4, 6, 10], 4) == 94837
assert product_sum([6, 8, 1, 7, 2, 10, 5, 9, 3, 4], 5) == 902055
assert product_sum([10, 3, 4, 9, 5, 8, 6, 7, 1, 2], 1) == 55
assert product_sum([7, 9, 4, 2, 3, 10, 8, 6, 5, 1], 9) == 10628640