Reslan's blog

help with binary search problem
By Reslan, history, 10 years ago, In English

Hello everyone what the idea to solve this problem I know that it may seems pretty easy problem for you , but for me as a beginer in binary search I couldn't even understand the tutorial !! thank in advance :D

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

Comments Comments (1)
| Write comment?
»
10 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

let x by the number that is more repeated after at most k operations , let Fx by the frecuency of x after at most k operations (Fx is the solution to the problem) let A by the array sorted let S by an array where S[i] = A [0] + A [1] +. . . + A[i] is easy to see that x is an element of A whitout make operations, if A[i] = x, then Fx = (i — j + 1) where j is the minimum index where it holds that ( (i — j + 1) * A [i] ) — (S [i] — S [j-1]) <= k, to find j, a binary search is done from [0 .... i].

→ Reply