242. How Many Times Does X Appear
Core1000 ms256 MBSolved by 0%
You are given n integers in non-decreasing order. Print how many times
x appears.
Scanning the array works and is O(n). With 200000 values and the array
already sorted, you can do far better: the copies of x are all next to each
other, so find where they start and where they end.
Two binary searches, subtract, done. Each is about eighteen steps rather than two hundred thousand.
Constraints - `1 ≤ n ≤ 200000` - `-1000000000 ≤ a[i] ≤ 1000000000`
Input
The first line contains two integers n and x.
The second line contains n integers in non-decreasing order.
Output
Print one integer, the number of times x appears.
Input5 2
1 2 2 2 3
Output3
Notehas three copies in the middle of the array
Input3 4
1 2 3
Output0
Noteis absent, so the answer is 0 rather than an error
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.