0

Following code finds if a given number is a perfect square in O(lg N). How can I avoid hard-coding the corner case if (num === 1) { return true; } given in the solution below? Any ideas?

var isPerfectSquare = function(num) {
    let floor = 0, ceiling = num, mid;

    // Corner case
    if (num === 1) {
        return true;
    }

    while (floor != ceiling) {
        mid = floor + (ceiling - floor) / 2 | 0;
        let mul = mid * mid;

        if (mul === num) {
            return true;
        }

        if (mul > num) {
            ceiling = mid;
        }
        else if (mul < num) {
            floor = mid+1;
        }   
    }
    return false;
};
Uthman
  • 9,251
  • 18
  • 74
  • 104
  • 1
    Possible duplicate of [Fastest way to determine if an integer's square root is an integer](http://stackoverflow.com/questions/295579/fastest-way-to-determine-if-an-integers-square-root-is-an-integer) – P0W Jan 17 '17 at 06:37
  • @P0W at least read first lines of a question before marking as duplicate. I don't need to find a faster solution. My question is regarding avoidance of a corner case. – Uthman Jan 17 '17 at 06:45
  • @P0W, proposed dupe is tagged [tag:java], even though the accepted answer is in C++ – Kaiido Jan 17 '17 at 06:46
  • @Kaiido its not a duplicate. I have updated the title of question. My last comment should also clarify kindly. – Uthman Jan 17 '17 at 06:49
  • 1
    @baltusaj, yes I know it's not, and it shouldn't have been interpreted as such even by not reading the question body. Tags already say it's not. – Kaiido Jan 17 '17 at 06:51
  • @baltusaj How much time do you think `if (num === 1) { return true; }` takes in you algorithm ? – P0W Jan 17 '17 at 06:52
  • @P0W why do you think I am asking about time it takes to find `if (num === 1) { return true; }`? – Uthman Jan 17 '17 at 06:53
  • @Kaiido A question tagged with algorithm and involving time complexity should have little to do with language preferences. – P0W Jan 17 '17 at 06:54
  • @P0W just to iterate again. I am not asking about time it takes for that corner case for I know its not significant. My question is purely for my understanding of how can I make my algorithm better to avoid the corner case without changing the O(lg N) time. Hope that clears my point. – Uthman Jan 17 '17 at 06:57
  • 1
    A small change would do the trick .. Please check solution below – AdityaReddy Jan 17 '17 at 08:39

2 Answers2

1

By keeping a smart invariant, we can change the code to require the equality check only once in the end. Should work for all input

var isPerfectSquare = function(num) {
    let floor = 0, ceiling = num+1, mid;
    // We will keep the invariants: floor*floor <= num,
    //   ceiling * ceiling > num

    while (ceiling - floor > 1) {
        mid = floor + (ceiling - floor) / 2 | 0;
        let mul = mid * mid;

        // Move one of floor/ceiling to mid
        // Retains the invariant!
        if (mul > num) {
            ceiling = mid;
        } else {
            floor = mid;
        }   
    }
    return floor * floor === num;
};

I might have screwed up the language syntax, but the idea should work.

Raziman T V
  • 480
  • 1
  • 4
  • 12
  • Looks quite clean. Thanks. But zero is considered not to be a perfect square by some mathmeticians. https://www.reference.com/math/zero-perfect-square-5560b33a2cfecf1. – Uthman Jan 18 '17 at 02:33
  • 1
    To avoid zero just start with floor=1 – Raziman T V Jan 18 '17 at 06:36
0

You can avoid the specific boundary case for num==1 by changing the condition in while loop to

while (floor < ceiling-1)

This will be sufficient as if the difference between floor & ceiling is 1 then you will run into an infinite loop as floor + ceiling-floor/2 will always be equal to floor when rounded off

I just tried with below Java implementation and it looks fine

public static void isPerfectSquare(int num){
     int low = 0;
     int high = num;
     int mid;
     while(low<high-1){
         mid = low + (high-low)/2;
         System.out.println("high-- " + high + " low-- " + low + " mid---" + mid);
         int square = mid*mid;
         if(square==num){
             System.out.println("Found ->" + mid);           
             break;
         }
         else if(square<num){
             low = mid;          
         }
         else if(square>num){
             high = mid;             
         }       
     }
    }
AdityaReddy
  • 3,625
  • 12
  • 25