Given an array arr of n integers in a single operation one can choose two indices, i and j, and delete arr[i] from the array if 2*arr[i] <= arr[j]
A particular element can be chosen at most once find the minimum possible size of the array after performing the operation any number of time, possibly zero.
Example:
Suppose n=7 and arr = [1, 2, 3, 4, 16, 32, 64]
In the first operation, choose 1 and 16 and delete 1 from the array as 2*1 <= 16. The array becomes [2, 3, 4, 16, 32, 64]
In the second operation, choose 2 and 32 and delete 2 from the array as 2*2 <= 32. The array becomes [3, 4, 16, 32, 64]
In the third operation, choose 4 and 64 and delete 4 from the array as 2*4 <= 64. The array becomes [3, 16, 32, 64]
Now the only element that has not been chosen is 3. There have to be two elements, arr[i] and arr[j], for a comparison to take place, so no more operations can occur. The minimum possible size of the array is 4. Note that there are multiple ways to achieve 4 elements in the final array after performing the operations.
Function description: complete the function getMinSize in the editor below. getMinSize has the following parameter:
arr[n]: an array of integers.
returns:
int: the minimum possible size of the array.
def getMinSize(arr):
arr.sort()
n = len(arr)
deleted = [False] * n
count = 0
for i in range(n):
if not deleted[i]:
for j in range(i+1, n):
if not deleted[j] and arr[i] * 2 <= arr[j]:
deleted[i] = True
deleted[j] = True
count += 1
break
return n - count
This solution can pass the example but will fail when the test case is {1, 2, 4, 6}. It outputs 3 but the expected answer is 2.
Your current code does not work because the algorithm logic does not solve the probem. It labels '1' and '2' as delete, and then check '4' and '6'. but it should label '1' and '4' and delete, and then check '2' and '6'.
Because 'A particular element can be chosen at most once',you could separate your sorted array into 2 half, and compare the elements of these 2 halfs one by one.
Below is the code modified from your code:
def getMinSize(arr):
arr.sort()
n = len(arr)
deleted = [False] * n
count = 0
j=int(n/2)
for i in range(int(n/2)):
while j < n:
if arr[i] * 2 <= arr[j]:
#delete i,and use j
count += 1
j+=1
break
j += 1
return n - count
print(f"Testing getMinSize(): {getMinSize([1, 2, 4, 6])}")