Why my problem going time limit exceeded even I am implementing binary search my solution
# | User | Rating |
---|---|---|
1 | tourist | 3993 |
2 | jiangly | 3743 |
3 | orzdevinwang | 3707 |
4 | Radewoosh | 3627 |
5 | jqdai0815 | 3620 |
6 | Benq | 3564 |
7 | Kevin114514 | 3443 |
8 | ksun48 | 3434 |
9 | Rewinding | 3397 |
10 | Um_nik | 3396 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 156 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
Why my problem going time limit exceeded even I am implementing binary search my solution
Name |
---|
Your solution uses
Array.LastIndexOf
. This Java function iterates over the complete array, so the complexity will again be O(n). Look with the binary search for the smallest element a[i] that is greater than x, then the answer is i.I am sorting then using binary Search but it is still giving TLE. Can you check this one and let me know why?
63616723
Your binary search implementation is wrong. The idea behind binary search is, that the search range gets halved each time. In your implementation you decrease the search range only by one (via
left++
andright--
), so the complexity is as bad as just doing a linear search.For a binary search you need something like
left = mid + 1
instead ofleft++
andright = mid-1
instead ofright--
. But no guarantee, that this is the only mistake. I only glanced over your code for a second.Btw, that's also a very long way of writing the binary search.
I would write it like that:
The idea behind my though process is: I sustain two invariants the complete program.
l
is the largest shop that I know of in which I can buy the candy. At the beginning I don't even know if I can buy it at the first shop, so I initialize it withl = -1
.r
is the smallest shop where I know that I can't buy the candy, so at the beginning it islist.size()
, since I don't know if I can buy from the last one or not.I want to know, how we could have done this problem if prices at some shops would be same?
Exactly the same way.
But we also have to keep track of the frequency of prices ?
No, that doesn't matter.
I wrote that in my code I find the largest shop that I know of in which I can buy the candy. This is maybe a little imprecise. Correctly it should be: I find the largest index such that I can buy from the shop corresponding to the index.
And that handles duplicates per default. E.g. if the prices are $$$2, 3, 5, 5, 6$$$ and I have $$$5$$$ coins. Then I find the index 3.
Thanks for the explanation ,I understood it
The following is a simple C++17 implementation using upper_bound function.
37844068
In your binary search implementation, if x equals to arr[mid] then you are using LastIndexOf (which has O(n) complexity) that's why you are getting TLE I recently solved this problem and I faced the same problem you need to replace LastIndexOf with binary search which finds the last occurrence of any element like this one.
Please don't copy the code try to understand it. Here is my solution for further reference Solution
come on man, its a 3 year old post.