B.i.b.e.r's blog

Interview Question Media NET
By B.i.b.e.r, history, 16 months ago, In English

Hello Everyone, Recently in one of my interview Rounds ,I got asked this question, I just wanted to know is there any optimal way to do this ? in less than 0(nlogn) or 0(n) Complexity

Given an array of Integers(positive and negative) and Target Element K ,you have to find minimum absolute difference between target element and subarray summ. Also there are going to be q queries where each time you will have different K

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

Comments Comments (3)
| Write comment?
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

do perfix sum, enumeration "l", Use multiset.lower_bound to find r

O(n log n)

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

    But there are q queries each time you will have different K so question gets more complex

    → Reply