Finding the number of integers that are a square and a cube at the same time

Question

I have written some code that takes two integers and returns the numbers of numbers that are both a square and a cube. I would like to know if there is a more efficient way to write this. I have only just started learning Java so any feedback would be greatly appreciated.

Scanner input=new Scanner(System.in);
double a=input.nextInt();
double b=input.nextInt();
int coolnumbers=0; //counter for the # of numbers that are a square and cube
for(double i=a; i<=b; i++){ 
    for(double j=1; j<=b; j++){
       if(i==Math.pow(j,6)){
         coolnumbers++;
         break;
       }
    }
}
System.out.println(coolnumbers);

Answer 1

Let's say a = 1, b = 1,000,000. Your code is a nested loop, each loop iterating a million times, for a total of one trillion tests. And I tell, out of my head, that the result is 10 and the numbers are 1, 2^6, 3^6, 4^6, 5^6, 6^6, 7^6, 8^6, 9^6 and 10^6.

The numbers that are both 2nd and 3rd powers are exactly the sixth powers of integers. So you can just iterate for i = 0, 1, 2, 3 etc., calculate j = i^6, then if j >= a and j <= b increase the counter, and if j > b then exit the loop. The time needed is proportional to the sixth root of b.

Even faster, if b was extremely large, calculate A = sixth root of a, round up to the nearest integer, and B = sixth root of b, rounded down to the nearest integer. The numbers from a to b that are sixth powers are exactly the sixth powers of the numbers from A to B, and there are B - A + 1 of them.

Answer 2

@JellybeanNewbie, and welcome to code review.

You ask about efficiency, and there are a few changes that jump out to me as possibilities for speeding things up. I'll make a few comments about other aspects of your code first, and then walk through the efficiency things.

---

double b=input.nextInt();

There are actually three little concerns on this line.

First is that b is not a very descriptive variable name. The code would be clearer if it were named something else, like upperBound.

Second, it is always worth being careful about what types your variables have. It's a bit of a red flag when you are getting an int and putting it into a double variable. There are good reasons to use doubles sometimes, but they can cause subtle bugs often associated with rounding error. If you definitely want to work with an integer it's usually worth keeping things as int. If not, perhaps you should be using something like nextDouble.

Third is that this is information that is coming from the user. As a general rule, it's worth checking all information that comes from the user, just to make sure that it makes sense. For example, it may be worth making sure that b is actually a number. It's also worth checking that b is bigger than a. Likewise if there's anything else that could make the code fall over, it is usually worth checking that they haven't used such an input as soon as possible.

---

for(double j=1; j<=b; j++){

This line is actually hiding a subtle bug. Suppose that your input for a is 0 and b is 2, which seems like a perfectly sensible pair of inputs. There are then two answers: both 0 and 1 are both squares and cubes. However your for loop starts at 1, which means it will skip right over considering 0. Now this bug will actually disappear completely with some of my efficiency suggestions, but I wanted to draw attention to it because it highlights an important lesson in testing code. That is, always remember to think about and test the edge cases, which are the biggest or smallest things that a bit of code can work with.

---

Now, for the efficiency bit. There is a useful proverb for getting code to go faster: "The fastest code is the code that isn't run."

Look again at the for loop with j in it. That loop is counting upwards, from 1 to b. For each number between 1 and b, it checks whether j to the power of 6 is exactly i. Now, let's suppose that b is a big sort of number, perhaps a million, so you're doing that check a million times. However, as soon a j to the power of 6 is greater than i, it's clear that none of the rest of those possible j values can be the number you want. After all, j keeps getting bigger, so j to the power of 6 will get bigger, and it's already too big. Once you notice that, you'll see that instead of checking a million possible values of j we only have to check ten.

That's a big improvement, but there is room do do better. Instead of checking possible values of j and seeing whether j to the power of 6 is i, you can just check the sixth root of i. (For example using Math.pow(i, 1.0/6.0) or Math.sqrt(Math.cbrt(i))). If that is an integer, then you've found a special number. And in the process, you can completely delete the second for loop.

There's a couple of tricks that I've used here. Think about the sixth root rather than counting up the sixth powers. Think about what happens as you start to count up. I'll end on a challenge. Can you find a way to use the same sorts of tricks to make the that first for loop shorter, and then disappear? I think you can solve this problem without any looping at all!

Answer 3

Welcoem JellybeanNewbie!

The first thing I noticed (I'm not a Java programmer) is that you have no way of knowing that b is greater than a. I would add a check in there to make sure you're going from smaller to bigger in your loops.