Problem Link - The Wave in Binary Search
Problem Statement:
Chef is stuck in the wavey world of polynomials. You are given all N roots of a polynomial P(x) = ∏ (x - a_i) for i = 1 to N The roots are pairwise distinct integers, but they are not given in any particular order.
To help Chef escape, you should answer Q queries (numbered 1 through Q). For each valid i, in the i-th query, you are given an integer x_i and you have to determine whether P(x_i) is positive, negative or 0.
Approach:
-
Sorting the Roots: Since the roots are pairwise distinct but given in an arbitrary order, they are sorted in increasing order.
-
Queries: For each query, you are given a number x. The goal is to determine whether P(x) is positive, negative, or zero. The key observation here is that the sign of P(x) depends on how many roots are less than x.
-
Binary Search: To efficiently determine the number of roots that are less than x, the function lower_bound is used. It returns the first index where a[i]≥x.
-
Checking for Zero: If x is a root of the polynomial, the output is 0 (since P(x)=0).
-
Determining the Sign of P(x):
- If x does not match any root, the number of terms in P(x) that are negative will determine the sign of the product.
- If x is smaller than an odd number of roots, the product will have an odd number of negative terms, making P(x) negative.
- If x is smaller than an even number of roots, the product will have an even number of negative terms, making P(x) positive.
Complexity:
- Time Complexity:
O(n logn)for sorting and for eachqqueriesO(q)we are performing lower_boundO(log n)so it will beO(q logn). Overall time complexity:O(n logn + q logn)→O((n+q) logn). - Space Complexity:
O(1)No additional space used.