LGCNSRT - Editorial



Author : Prasoon Jain
Tester : Prasoon Jain
Editorialist : Prasoon Jain




Math, binary search


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.


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).


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);
          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) {
            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;

submit button is not visible . and problem is not visible in practice section/Link.
& Thanks for Editorial .

The problem will soon move to the practice section, and then you will be able to submit the solutions. Thanks.

O(1) solution if we implement this