Write an efficient algorithm in python to solve math problem

Question

I can't came up with an algorithm to solve the following problem:

1. Generate an array of first n prime numbers.
2. Remove k numbers from this array in such way that after concatenating all numbers left we get the largest possible result.

E.G.

Input: 4 2

• First value(4) is n

• Second value(2) is k

• Array [2, 3, 5, 7] is generated

• the program have to remove numbers 2 and 3 from this array(to get 57, which is the max possible number we can get from this array after deleting k numbers and merging all the numbers left together).
• e.g. If it removes 2 and 7 - we will get 35(which is not the max number). So, this solution is wrong.

Output: 57

This is the code I have so far:

def getInputedVals():
 return [int(el) for el in input().split(" ")]
def get_primes_array(x):
 primes = []
 a = 2
 # for a in range(2, 10000):
 while(len(primes) != x):
 for b in range(2, a):
 if a % b == 0:
 break
 else:
 primes.append(a)
 a += 1
 if len(primes) == x:
 return primes
def combine_numbers(nums):
 s = [str(i) for i in nums]
 return int("".join(s))
# Algorithm to find the max number should be written here
def get_result(nums, n_nums_to_delete):
 print("algorithm goes here")
def main(item):
 primes = get_primes_array(item["n_first"])
 summed = sum(primes)
 # print(get_result(primes, item["n_nums_to_delete"]))
 print("Primes: ", primes)
n_first, n_nums_to_delete = getInputedVals()
item = {"n_first": n_first, "n_nums_to_delete": n_nums_to_delete}
main(item)

• Robert Dodier: Well, the simplest way to approach a problem like this is exhaustive search. That just means, enumerate all the potential solutions, and see which one is best. In this case it would look like this: find all sublists of your primes list which have k elements removed, then form the concatenated number, then see which concatenated number is largest. There will be (n choose k) sublists and therefore that many concatenated numbers to look at. (n choose k) can be a large number, but my advice is get this simple algorithm working first and then look at ways to make it more space or time efficient.
• btilly: Is there any case when the right thing to do isn't to remove the first k numbers?
• Staxxx6: @btilly No. k numbers have to be removed
• btilly: @Staxxx6 Yes, but which k numbers? If the best choice is always the first k then the problem becomes much simpler.

Answer 1

You have the answer, sort your results and take the sorted list starting from the n_nums_to_delete :

def get_result(nums, n_nums_to_delete):
 return sorted(nums)[n_nums_to_delete:]

As @Yuri Ginsburg mentioned in the comment, your prime number list is already sorted, so you can simply do :

def get_result(nums, n_nums_to_delete):
 return nums[n_nums_to_delete:]