CODEWITHSUNDEEP
java
SuperMan
SuperMan

Reputation: 3584

Interview: Find the whole cubes between range of two Integers

I just gave a coding interview on codility

I was asked the to implement the following, but i was not able to finish it in 20 minutes, now I am here to get ideas form this community

Write a function public int whole_cubes_count ( int A,int B ) where it should return whole cubes within the range

For example if A=8 and B=65, all the possible cubes in the range are 2^3 =8 , 3^3 =27 and 4^3=64, so the function should return count 3

I was not able to figure out how to identify a number as whole cube. How do I solve this problem?

A and B can have range from [-20000 to 20000]

This is what I tried

import java.util.Scanner;
class Solution1 {
  public int whole_cubes_count ( int A,int B ) {
      int count =0;

    while(A<=B)
    {
        double v = Math.pow(A, 1 / 3); // << What goes here?
        System.out.println(v);
        if (v<=B)
            {
            count=count+1;
            }
        A =A +1;
    }
    return count ;
  }

  public static void main(String[] args) 
  {
    System.out.println("Enter 1st Number");
    Scanner scan = new Scanner(System.in);
    int s1 = scan.nextInt();
    System.out.println("Enter 2nd Number");
    //Scanner scan = new Scanner(System.in);
    int s2 = scan.nextInt();
    Solution1 n = new Solution1();
     System.out.println(n.whole_cubes_count (s1,s2));
  }
}

Upvotes: 3

Views: 4717

Answers (5)

Tim Babych
Tim Babych

Reputation: 3454

Well, it can be computed with O(1) complexity, we will need to find the largest cube that fits into the range, and the smallest one. All those that are between will obviously also be inside.

def n_cubes(A, B):
    a_cr = int(math.ceil(cube_root(A)))
    b_cr = int(math.floor(cube_root(B)))

    if b_cr >= a_cr:
        return b_cr - a_cr + 1
    return 0

just make sure your cube_root returns integers for actual cubes. Complete solution as gist https://gist.github.com/tymofij/9035744

Upvotes: 1

Eugene Grednov
Eugene Grednov

Reputation: 1

The solution suggested by @Tim is faster than the one provided by @Erick, especially when A...B range increased. Let me quote the ground from github here: "one can notice that x³ > y³ for any x > y. (that is called monotonic function) therefore for any x that lies in ∛A ≤ x ≤ ∛B, cube would fit: A ≤ x³ ≤ B

So to get number of cubes which lie within A..B, you can simply count number of integers between ∛A and ∛B. And number of integers between two numbers is their difference."

It seems perfectly correct, isn't it? It works for any power, not only for cube. Here is my port of cube_root method for java:

/*
 * make sure your cube_root returns integers for actual cubes
 */
static double cubeRoot(int x) {
    //negative number cannot be raised to a fractional power
    double res = Math.copySign(Math.pow(Math.abs(x), (1.0d/3)) , x);
    long rounded_res = symmetricRound(res);
    if (rounded_res * rounded_res * rounded_res == x)
        return rounded_res;
    else
        return res;
}

private static long symmetricRound( double d ) {
    return d < 0 ? - Math.round( -d ) : Math.round( d );
}

I am aware of Math.cbrt in java but with Math.pow approach it is easy to generalize the solution for other exponents.

Upvotes: 0

Magesh Pachiyappan
Magesh Pachiyappan

Reputation: 146

int countNoOfCubes(int a, int b) {
        int count = 0;
        for (int startsCube = (int) Math.ceil(Math.cbrt(a)); Math.pow(
                startsCube, 3.0) <= b; startsCube++) {
            count++;
        }
        return count;
    }

Upvotes: 0

Erick Robertson
Erick Robertson

Reputation: 33082

Down and dirty, that's what I say.

If you only have 20 minutes, then they shouldn't expect super-optimized code. So don't even try. Play to the constraints of the system which say only +20,000 to -20,000 as the range. You know the cube values have to be within 27, since 27 * 27 * 27 = 19683.

public int whole_cubes_count(int a, int b) {
    int count = 0;
    int cube;
    for (int x = -27; x <= 27; x++) {
        cube = x * x * x;
        if ((cube >= a) && (cube <= b))
            count++;
    }
    return count;
}

Upvotes: 7

Code-Apprentice
Code-Apprentice

Reputation: 83557

For the positive cubes:

i = 1
while i^3 < max
    ++i

Similarly for the negative cubes but with an absolute value in the comparison.

To make this more general, you need to find the value of i where i^3 >= min, in the case that both min and max are positive. A similar solution works if both min and max are negative.

Upvotes: 7

Related Questions