Dracula1203's blog

Most Occurring Number After K Increments
By Dracula1203, history, 4 years ago, In English

This is my first blog post.

It would be great if someone could explain their approach.

You are given a list of integers nums and an integer k. Consider an operation where you increment any one element once. Given that you can perform this at most k times, return the resulting value of the most frequently occurring number. If there's more than one solution, pick the smallest possible number.

Constraints : n ≤ 100,000 where n is the length of nums.

TestCase : nums = [1, 1, 1, 2, 2, 2, 4, 4, 4, 4] k = 3

Output : 2

Explanation :

After we increment the 1s, we get [2, 2, 2, 2, 2, 2, 4, 4, 4, 4]

**Link : https://binarysearch.io/problems/Most-Occurring-Number-After-K-Increments**

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

Comments Comments (5)
| Write comment?
»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

  1. shows that the response is an element in the array.

  2. sort the array and find out how to extend a specific element (to right? to left?).

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I'm sorry Can you explain it in little brief.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 3   Vote: I like it +10 Vote: I do not like it

      • first, the answer has to be an element greater than or equal to the minimum.

      • suppose the response is not an element in the array, then there is a maximum element in my original array that is less than that element.

      • then we can remove (final number of repetitions) x (answer — maximum element found) and reduce the number of operations and at the same time find a smaller result (this is a contradiction, the answer is not smaller).

      • now that we know the answer is an element of the array, we can fix this and not think of larger elements.

      • Once the answer is fixed, we can greedily improve the answer, choosing the elements that are larger but at the same time smaller than my answer and gradually increasing them.

      • this sounds like an $$$O(n^2)$$$, but it is not the case, we can make an improvement if we do a binary search, we set a position in the ordered array (we can use sort function with a complexity of $$$O(n \log n)$$$) and fix as far as I can extend said element to the left (make all a fixed number of elements equal to the answer), we can do this by carrying accumulated and checking that $$$({answer} ~x~ {len}) - ({sum}_i - {sum}_{i - len}) \le k$$$.

      • final complexity $$$O(n \log n)$$$, as a note, if you had the ordered array in the input, there would be a linear solution with two pointers.

      P.S: There are several more approaches, this would not be the only one, it is not necessary to use binary search but at the same time I consider that it is very useful and simplifies problems a lot.

      → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it
  1. sort the array.
  2. for each index i, find the closest index to its right such that numbers of steps remain <= k. Let that index be idx, then number of steps will be (a[idx] — a[i]) + (a[idx] — a[i+1]) + ... + (a[idx] — a[idx]) which is equal to (idx — i + 1) * a[idx] — (dp[idx] — dp[i-1]) where dp[i] denotes cumulative sum. Among all these find the one with maximum length i.e. idx — i + 1.

Solution

Harder variant: https://binarysearch.io/problems/Longest-Equivalent-Sublist-After-K-Increments

→ Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

history repeats itself

→ Reply