PROBLEM LINK
Author : Prasoon Jain
Tester : Prasoon Jain
Editorialist : Prasoon Jain
DIFFICULTY
SIMPLE
PREREQUISITE
Math, binary search
PROBLEM
You are given a cubic equation x^3+x^2+x+k= v.
For every test case you will be given values of k and v. In each test case determine the value of x.
It is guaranteed that x exists and is always an Integer.
EXPLANATION
The simple brute force approach is to iterate over all possible values of x, and check if it satisfies the given equation and the x which satisfies the equation is the answer.
But if we closely observe the properties of given cubic equation, we see that this question can also be solved using Binary Search. It is given here that x, k, v are always non-negative numbers, and under these conditions cubic equations have exactly one real root.
This implies that for each value of x, we have unique v, and if all the variables of equation are positive, then we found that as the value of x increases, v will also increase.
The main condition to perform a Binary Search is that the sequence must be monotonous i.e., it must be either increasing or decreasing. And in our question we proved that that the equation is always increasing, so binary search can be used here.
If we do a linear search to find the value of x it will lead to O(n) time complexity, but doing a binary search on x, we can reduce the time complexity to O(logn).
Solution:
Editorialist's Solution
import java.util.Scanner;
public class CubicSol {
static long calAns(int x, int k) {
long ans = 0L;
ans = (long) (pow(x, 3) + pow(x, 2) + x + k);
return ans;
}
// method to find power
public static long pow(long a, long b) {
long result = 1;
while (b > 0) {
if (b % 2 != 0) {
result = (result * a);
b--;
}
a = (a * a);
b /= 2;
}
return result;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t > 0) {
int k = sc.nextInt();
long ans = sc.nextLong();
int x = 0;
int l = 0;
int r = 1000000; // x must be less than 10^6
// Binary Search on x
int i = 0;
while (l <= r) {
i++;
int m = (l + r) / 2;
if (calAns(m, k) > ans) {
r = m - 1;
}
else if (calAns(m, k) < ans) {
l = m + 1;
}
else {
x = m;
break;
}
}
System.out.println(x);
t--;
}
}
}