Astroflexx's blog

can somebody help me solve this problem please? no idea how to solve it
By Astroflexx, history, 3 months ago, In English

Given an array of integers and an integer m, in one operation, choose atmost m numbers of the array and increment them.

What is the minimum no of operations to make all the elements in the array equal?

1 <= nums[i] <= 1e5

1 <= m <= 1e5

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
3 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

.

→ Reply
»
3 months ago, # |
← Rev. 4   Vote: I like it +2 Vote: I do not like it

assuming the numbers are incremented by one i think you can just sort the array and the biggest value minus the smallest would be the answer

why are you people upvoting my wrong solution this solution is wrong i posted the right one in the replies grahhhhh

→ Reply
  • »
    »
    3 months ago, # ^ |
    ← Rev. 7   Vote: I like it 0 Vote: I do not like it

    nevermind i realized the issue with this approach i am so terrible at this. this doesnt work if the m integer is smaller

    then i think you just sort an array and then while the smallest integer is smaller than the biggest you increment the smallest integers in the array with a for loop if the array is not smaller then the loop breaks

    we add 1 to the counter and sort the array at the end of a while loop as well

    i have no idea how to phrase any of this better i myself am probably on the same level of coding

    heres the lump of python code that I THINK works:

    t = int(input())  # num of iterations


def calc():
    c = 0
    a = list(map(int, input().split()))
    m = int(input())
    a.sort()

    while a[0] < a[len(a)-1]:

        a.sort()
        for i in range(m):
            if a[i] < a[len(a)-1]:
                a[i] = a[i] + 1
            else:
                break
        a.sort() # added this after posting and realizing that sometimes the first num in the array can be the same size as the last but not the other ones
        c = c + 1  # the loop that repeats while the smallest int is smaller than the biggest; we check if the value is smaller than the biggest and if it is, we increment it; we also add 1 to the counter each "while" repetition

    print(c)


for i in range(t):
    calc()

# i think this kinda works
    → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

bro do paste the question link

→ Reply
»
3 months ago, # |
← Rev. 4   Vote: I like it +8 Vote: I do not like it

I think this works.

def solve(nums, m):
    mx = max(nums)
    a = [mx - i for i in nums]
    return max(max(a), (sum(a) + m - 1) // m)
→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i think u just have to sum the difference between max and every other element in the array, and then divide the sum by m, ceil(sum), to ensure that if there were remainders, it can be rounded up.

→ Reply