Equalizing Array Elements
Given an array of integers, transform it so that at least a certain number of elements in the array are equal. To achieve this, you can (Equalizing array elements hackerrank solution python)
perform an operation where you select an element in the array and divide it by the given division parameter using integer division.
What is the minimum number of operations that must be performed to achieve this goal on a certain array?
For example, let's say arr = [1, 2, 3, 4, 5). The desired number of equal elements is denoted as threshold = 3, and the division
parameter is d = 2. If you divide the value 4 once and the value 5 once using integer division, you get the array [1, 2, 3, 2, 2], which
contains 3 equal elements. There is no way to achieve this in less than 2 operations. Therefore, the answer is 2.
Function Description ( Equalizing Array Elements Hackerrank Solution python)
Complete the function minOperations in the editor below.
min Operations has the following parameter(s):
int arr[n]: an array of integers
int threshold: the minimum number of desired equal elements in the array
int d: the division parameter used to divide an element in a single operation
Returns:
int: the minimum number of operations required to have at least threshold number of equal elements in the array
Constraints
• 1sns 3*104
• 1 s arr[i]< 2*105
1 s thresholds n
• 2 sds 1000
Input Format For Custom Testing
The first line contains an integer, n, denoting the size of the array.
Each line i of the n subsequent lines (where 0 si<n) contains an integer that describes arr[i].
The next line contains an integer, threshold, denoting the minimum number of desired equal elements in the array.
The next line contains an integer, d, denoting the division parameter.
Sample Case 0
Sample Input For Custom Testing
4
64
30
25
33
2
2
Sample Output
3
Explanation
In this case, arr = [64, 30, 25, 33), threshold = 2, and the division parameter d = 2. In other words, the minimum required number
of equal elements is 2, and in one operation we can divide a single element by 2 using integer division. If we divide 64 twice to get
16, and we divide 33 once to also get 16, Then the array becomes [16, 30, 25, 16), which has 2 equal elements. There is no way to
get at least 2 equal elements with fewer than 3 operations. Therefore, the answer is 3.
Sample Case 1
Sample Input For Custom Testing
4
1
2
3
4
4
3
Sample Output
6
Explanation
In this case, the arr = [1, 2, 3, 4], threshold = 4, and the division parameter d = 3. In other words, the minimum required number
of equal elements is 4, and in one operation we can divide a single element by 3 using integer division. The only way to get all 4
elements to be equal is to divide all of them so they all become 0. One operation is required to convert 1 to 0, and another single
operation is required to convert 2 to 0. Two operations are required to convert 3 to 0, and another two operations are needed to
convert 4 to 0. Therefore, the total number of required operations is 1+1+2+2 = 6.
#!/bin/python3
import math
import os
import random
import re
import sys
from collections import defaultdict
#
# Complete the 'minOperations' function below.
#
# The function is expected to return an INTEGER.
# The function accepts following parameters:
# 1. INTEGER_ARRAY arr
# 2. INTEGER threshold
# 3. INTEGER d
#
def minOperations(arr, threshold, d):
# dp[i] := [count of i values, number of steps]
dp = defaultdict(lambda: [0, 0])
arr.sort()
ans = sys.maxsize
for x in arr:
steps = 0
while True:
dp[x][0] += 1
dp[x][1] += steps
if dp[x][0] >= threshold:
ans = min(ans, dp[x][1])
if x == 0:
break
x //= d
steps += 1
return ans
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
arr_count = int(input().strip())
arr = []
for _ in range(arr_count):
arr_item = int(input().strip())
arr.append(arr_item)
threshold = int(input().strip())
d = int(input().strip())
result = minOperations(arr, threshold, d)
fptr.write(str(result) + '\n')
fptr.close()