We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Sherlock and Counting
Sherlock and Counting
Sort by
recency
|
32 Discussions
|
Please Login in order to post a comment
Python 3: ans: 1~left root + right root ~n-1
If you use the quadratic formula be careful with (b^2 - 4.a.c == 0). Cheers everyone.
Btw, it's also possible to pass test cases in this perticular problem using Binary Search. just find the max possible i between 1 and n/2, where, i.(n-i) <= n.k and the answer is two times that. also need to take care of the edge case of n/2 . (n - n/2) <= n . k.
Here is my solution: (Just need to analize quadratic inequality, and analize discriminant, there is the trick)
static int solve(int n, int k) { double disc = 1d*n * n - 4d * n * k; if (disc < 0) { return n - 1; } double x1 = (n + Math.sqrt(disc)) / 2; double x2 = (n - Math.sqrt(disc)) / 2;
Well my solution is based on the fact that since is positive that means the first coefficient will be positive so the parabola will be concave up.
From the parabola we can easily conclude that the solution is between 1 and floor of first root and from ceil of second root to n only for those values the equation will be greater or equal to zero. If the discriminant is imaginery then that means all values upto n will result in a positive answer for the equation.