# Positive or Negative

See the original problem on HackerRank.

## Solutions

The linear solution is simple: just count the frequencies of both negative and positive integers.

However, the optimal solution is more interesting: leveraging the sorted nature of the array, we can exploit binary search. Here’s where a crucial detail comes into play: 0 is neither positive nor negative. Consequently, searching for 0 presents us with an opportunity to swiftly determine the count of positive and negative integers.

In essence, we need to recall two fundamental concepts regarding binary searches:

• Lower bound: locates a specified element or the next one if the specified element is absent;
• Upper bound: locates the next element after the specified one.

Clearly, both are binary searches, operating in logarithmic time.

The idea here is to find both lower bound and upper bound of 0:

• all the elements before the lower bound of 0 are necessarily negative (lower bound of 0 finds either 0 or the first positive);
• all the elements after the upper bound of 0 are necessarily positive (upper bound of 0 finds the first positive).

For example:

 1 2  0 1 2 3 4 5 -4 -2 -1 0 5 7 
• lower bound(0)=3, indeed the number of negative integers is 3-0=3
• upper bound(0)=4, indeed the number of positive integers is 5-4=1

Another example without 0:

 1 2  0 1 2 3 4 -4 -2 -1 5 7 
• lower bound(0)=3, indeed the number of negative integers is still 3-0=3
• upper bound(0)=4, indeed the number of positive integers is still 4-3=1

Another example with more 0:

 1 2  0 1 2 3 4 5 6 7 8 9 -1 -1 0 0 0 5 7 8 9 10 
• lower bound(0)=2, indeed the number of negative integers is 2-0=2
• upper bound(0)=5, indeed the number of positive integers is 10-5=5

The most concise C++ code is here below:

 1 2  auto [b,e] = equal_range(begin(nums), end(nums), 0); return max(distance(begin(nums), b), distance(e, end(nums))); 

equal_range combines both lower_bound and upper_bound into a single function call.

In Python, for example, we explicitly call both:

 1 2 3  neg = bisect_left(nums, 0) pos = len(nums) - bisect_right(nums, 0) return max(neg, pos) 
We've worked on this challenge in these gyms: modena