Test case failing

#1

Can you please help , don’t know why 2 test cases are failing.
Also is the best approach brute force to do this?

#2

@bhavik911,
you binary search.

For every possible mid obtained by using binary search we will check of it is the best suitable candidate or not for becoming the Kth root and then we reduce the search space of the binary search according to the mid value. If mid^k is greater than N then we will find the best suitable value from left to mid-1 otherwise we will find much larger value by finding it from mid+1 to right.

Example:

initially hi = 10^6, and k = 10, n = 1000000000000000

Now we keep multiplying mid until it either exceeds n or we multiply it k number of times. as seen in this for loop ( for (int i = 1; i <= k; i++) )

Now initially:
mid is 5001 (not our final answer)
lo is 1
hi is 5000

After that we half mid by (lo+hi+1)/2, mid becomes: 2501. But again this is not our final answer. Now, lo is 1 and hi is 2500.
And we check until we get our answer as 31.

#3

Everytime I am running loop for 10^15 it gets overflowed because value of mid is too alrge

#4

How can we get around this??

#5

I tried another approach like in case of infinite no but it causes TLE

#6

Please suggest how to tackle this now

#7

@bhavik911,
can you please share your code?

#8 
Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        for (int i = 0; i < n; i++) {
            long n1 = scanner.nextLong();
            int n2 = scanner.nextInt();
            System.out.println(powered(n1, n2));
        }
    }


    public static long powered(long n, int power) {
        long lo = 1;
        long high = n;
        long ans = 1;
        while (lo <= high) {
            long mid = lo + (high - lo) / 2;
            long result = 1;
            for (int i = 1; i <= power; i++) {
                if (result > n) {
                    high = mid - 1;
                    break;
                }
                result *= mid;
            }
            if (result == n) {
                return mid;
            } else {
                ans = mid;
                lo = mid + 1;
            }
        }
        return ans;
    }
#9 
package Arrays;

import java.util.Scanner;

public class KthRootAnotherThought {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        for (int i = 0; i < n; i++) {
            long n1 = scanner.nextLong();
            int n2 = scanner.nextInt();
            System.out.println(binarySearcher(n1, n2));
        }
    }

    public static long Pow(long n, int pow) {
        long result = 1;
        for (int i = 1; i <= pow; i++) {
            result *= n;
        }
        return result;
    }

    public static int binaryStarter(long n, int pow) {
        int result = 1;
        long compare = 1;
        while (compare < n) {
            compare = Pow(result, pow);
            result *= 2;
        }
        return result;
    }

    public static long binarySearcher(long n, int pow) {
        int start = binaryStarter(n, pow);
        if (Pow(start, pow) == n) {
            return start;
        }
        long lo = 1;
        long ans = 1;
        long high = start - 1;
        while (lo <= high) {
            long mid = lo + (high - lo) / 2;
            if (Pow(mid, pow) == n) {
                return mid;
            } else if (Pow(mid, pow) < n) {
                ans = mid;
                lo = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return ans;
    }
}
#10

I have tried these two but both causes overflow

#11

I converted into double now but in this case test case 1 is failing

#12

please tell the error in the code if any

#13

@bhavik911,
https://ide.codingblocks.com/s/290851 corrected code.

Changes I made:

  1. Use long everywhere in code. Take input as long as well.
  2. Set high as 10^8.
  3. While calculating mid, add 1/2 to prevent overflow. (mid = (lo+high+1)/2
  4. Set low as mid and high as mid-1. Also, ans will be equal to high.
#14

hey are we are setting high = 10^8 how arr we ensuring that there are not x above that i mean?

#15

Also why is doublr code not working , I even converted my final ans to int

#16

So we have to explicitly check for 1 here??? Also we are taking 10^8 explicitly??

#17

???(…)sadsads

#18

@bhavik911,
we are setting high as 10^8 to avoid overflow. As we already added a test case for 1 i.e. if k==1, return n. In case n is max i.e. 10^15, and k=1, we will return 10^15. In case k=2, the max value x can take is less than 10^8.

1 Like
#19

@bhavik911,
Double code is not working because in the input you are not taking input as long. Hence the error

#20 
package Arrays;

import java.util.Scanner;

public class KthRootBetterAppraoch {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        double n = scanner.nextDouble();
        for (double i = 0; i < n; i++) {
            double n1 = scanner.nextDouble();
            double n2 = scanner.nextDouble();
            System.out.println(powered(n1, n2));
        }
    }


    public static long powered(double n, double power) {
        double lo = 1;
        double high = n;
        double ans = 1;
        while (lo <= high) {
            double mid = lo + (high - lo) / 2;
            double result = 1;
            for (double i = 1; i <= power; i++) {
                if (result > n) {
                    break;
                }
                result *= mid;
            }
            if (result == n) {
                return (long) mid;
            } else if (result < n) {
                ans = mid;
                lo = (long) mid + 1;
            } else {
                high = (long) mid - 1;
            }
        }
        return (long) ans;
    }
}

THis is my double code , what changes should i do?