CODEWITHSUNDEEP
pythonpython-3.xperformance
flsantos0101
flsantos0101

Reputation: 3

Itertools.combinations() raising Time Limit Exceeded

I am trying to solve this Python coding problem:

Description: Teacher Ambrosio is teaching binary numbers to his daughter Ambrosinita, so he decided to create a game.

Ambrosio will give N numbers to Ambrosinita, who can choose K numbers among the initial N. For each number chosen, she earns a score equivalent to the number of 1's using the binary representation of the number.

Help Ambrosinita to find how many points she can earn.

Entry:

The first input line contains an integer T, which indicates the number of test cases.

Each test case starts with a line containing integers N(total numbers) and K(numbers that can be chosen).

The last input line of each case contains N integers, representing the numbers that Ambrosinita can choose.

Output:

For each test case print a line containing how many points Ambrosinita can earn.

1 ≤ T ≤ 10

1 ≤ N ≤ 10^3

0 ≤ K ≤ N

0 ≤ Numbers ≤10^5

There's an execution time limit of 2 seconds. I am getting a TLE Error, but the output is the same as expected. Thus, inputs must have a certain length.

Here's my code:

import itertools

test_cases = int(input())

def binary(num):
    return format(num,'b')

def filter_string_1s(string):
    aux = ''
    for i in string:
        if i == '1':
            aux += i
    return aux

for i in range(test_cases):
    k = input().split()
    k = int(k[1])
    values = input().split()
    values = [int(i) for i in values]
    values = [filter_string_1s(str(binary(i))) for i in values]
    bin_values = []
    for combination in itertools.combinations(values,k):
        aux = 0
        for bin_number in combination:
            for i in bin_number:
                if i == '1':
                    aux += 1
        bin_values.append(aux)
    print(max(bin_values))

Question: What steps should I take to optimize it in order to solve the problem within the execution time limit?

TLE = Time Limit Exceeded

Upvotes: 0

Views: 690

Answers (3)

flsantos0101
flsantos0101

Reputation: 3

Solved! Thanks everyone.

Code:

test_cases = int(input())

for i in range(test_cases):
    k = input().split()
    k = int(k[1])
    nums = input().split()
    nums = [format(int(i),'b').count('1') for i in nums]
    nums.sort()
    sum = 0
    for i in range(k):
        sum += nums[-1]
        del nums[-1]
    print(sum)

Upvotes: 0

Alain T.
Alain T.

Reputation: 42143

The maximum points she can make will be by selecting the K numbers that have the most 1 bits. So you simply need to compute the points for each number and take the top K.

for example:

import random

def maxPoints(K,N=None,numbers=None):
    numbers = numbers or [random.randrange(0,100001) for _ in range(N)]
    points  = sorted(bin(n).count("1") for n in numbers)
    return sum(points[-K:])

mp = maxPoints(3,numbers=[1,2,3,4,5])
print(mp) # 5

mp = maxPoints(1000,1000) 
print(mp) # will return instantly

Upvotes: 0

Prune
Prune

Reputation: 77857

This is a "top-k" problem, not a problem requiring "k" combinations. For sake of reading, let's pick N = 990, K = 7. You need to choose the top 7 scores in a list of 990.

You did this by generating C(990, 7) = 912,459,983,564,271,542,400 combinations, and then determining how many 1 bits are in each of the 7 numbers in each combination. This is why you're running out of time: you have 990 numbers to consider, but you're repeating the bit count gazillions of times for each number in the input.

Knock it off. All you need is to go through that list once and keep the top 7 bit counts. There are no interactions between the 7 numbers in the list. In fact you don't even have to report the numbers, merely the total score.

Start with a list of seven zeros. Now iterate through all 990 numbers. Any time you find a bit-count larger than the smallest element of the list (keep it sorted for ease of reference), then replace it with the new score (and re-sort). At the end of all 990 numbers, sum the list.

Also counting bits is much easier than you're doing. Convert the int to a binary string and use str.count(1) to see how many 1 bits are in it.

Upvotes: 1

Related Questions