**Objective**: Given an integer check whether it is a perfect square.

**Example**:

number = 37 Output: false number = 49 Output: true

This is fun puzzle which is asked in the interview.

**Approach**:

- Say number is n.
- Start a loop from 1 to n/2.
- During iteration, for every integer ‘i’, calculate x = i*i.
- Now with this ‘x’ there are 3 possibilities.
- If x == n then n is a perfect square, return true
- If x > n then x has crossed the n, n is not perfect square. Return false
- If above step a or b are not true then continue.

Time Complexity: O(sqrt(n))

**Code**:

public class ValidateSquare { | |

public static boolean isSquare(int n){ | |

if(n==0 || n==1) | |

return true; | |

for (int i = 0; i <=n/2 ; i++) { | |

int x = i*i; | |

if(x==n) | |

return true; | |

else if (n<x) | |

return false; | |

else | |

continue; | |

} | |

return false; | |

} | |

public static void main(String[] args) { | |

int n = 37; | |

System.out.println(n + " is square: " + isSquare(n)); | |

n = 49; | |

System.out.println(n + " is square: " + isSquare(n)); | |

} | |

} |

**Output**:

37 is square: false 49 is square: true

How about number 1? 1 is a perfect square. The above implementation will return false.