Friday, September 12, 2014

Program to find whether a number is a perfect square or not


You can write an algorithm in linear time something like below

for(int i=1; i<numberToCheck; i++) {
    if(i*i==numberToCheck) {
        return true;
        break;
    }
    return false;
}

The above code can be optimized as follows, since we are sure that the number of times it has to be traversed is less than or equal to half the size of the input number we can divide it by 2.

for(int i=1; i<numberToCheck/2; i++) {
    if(i*i==numberToCheck) {
        return true;
        break;
    }
    return false;
}

Optimized? Not quite... We can still optimize it to <=sqrt(input) number of times!
/**
 * Created by Arun on 9/12/14.
 */
public class Square {

    public static boolean findPerfectSquare(int a) {
        int currentSquare = 1;
        for(int i=1;currentSquare<a;i++) {
            System.out.println(i);
            if(i*i==a) {
                return true;
            }
            currentSquare = i * i;
        }
        return false;
    }

    public static void main(String args[]) {
        System.out.println(findPerfectSquare(1222));

    }
}

No comments:

Post a Comment