Perfect Square - The Coding Shala

Home >> Interview Questions >> Perfect Square

Check if a given number is perfect square or not

In this post, we will see how to check if a given number is a perfect square or not. Given a positive integer num, write a function that returns True if num is a perfect square else False.
Note: Do not use any built-in library function such as sqrt. 

Example 1:

Input: 16

Output: true

Example 2:

Input: 14
Output: false

Java Program to check a perfect square

Approach:
We can use a binary search to check if the given number is a perfect square or not instead of checking number one by one.
Java Code: 

class Solution {
    public boolean isPerfectSquare(int num) {
        if(num == 1) return true;
        int left = 1;
        int right = num/2;
        while(left < right){
            int mid = left + (right-left)/2;
            if((long)mid*mid == (long)num) return true;
            if((long)mid*mid > (long)num) right = mid-1;
            else left = mid+1;
        }
        if((long)right*right == (long)num) return true;
        return false;
    }
}


Other Posts You May Like
Please leave a comment below if you like this post or found some error, it will help me to improve my content.
By

Comments

Post a Comment

Popular Posts from this Blog

Longest Substring Without Repeating Characters Java Program - The Coding Shala

Home >> Interview Questions >> Longest Substring without repeating characters Longest Substring Without Repeating Characters Java Program In this post, you will learn how to find the length of the longest substring without repeating characters in a string and its Java solution. Given a string, find the length of the longest substring without repeating characters. Example 1: Input: "abcabcbb" Output: 3 Explanation: The answer is "abc", with a length of 3. Example 2: Input: "bbbbb" Output: 1 Explanation: The answer is "b", with a length of 1. Example 3: Input: "pwwkew" Output: 3 Java Solution of Longest Substring without Repeating Characters Approach 1: Using brute force by checking all the substrings.  We'll use HashSet to check if characters are unique or not. Time complexity: O(n^2) Space Complexity: O(n) Java Program:  class Solution { public i...
Read more

Anti Diagonals - The Coding Shala

Image
Home >> Interview Questions >> Anti Diagonals Anti Diagonals Java Solution Give an N*N square matrix, return an array of its anti-diagonals. Look at the example for more details. Example: Input: 1 2 3 7 8 9 4 5 6 Return the following : [ [1], [2, 4], [3, 5, 7], [6, 8], [9] ] Input : 1 2 3 4 Return the following : [ [1], [2, 3], [4] ] Anti Diagonals Java Solution 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 public class Solution { public ArrayList < ArrayList < Integer >> diagonal ( ArrayList < ArrayList < Integer >> A ) { ArrayList < ArrayList < Integer >> ans = new ArrayList < ArrayList < Integer >>(); int N = A . size (); int i = N - 1 ; while ( i >= 0 ){ ArrayList < Integer > tmp = new ArrayList < Integer >(); ...
Read more

Spiral Order Matrix II - The Coding Shala

Image
Home >> Interview Questions >> Spiral Order matrix 2 Spiral Order Matrix II Problem Solution Given an integer n, generate a square matrix filled with elements from 1 to n 2  in spiral order. Example: Given n = 3, You should return the following matrix: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ] Solution: (Java) The concept is the same as how to print the Spiral Order Matrix. Approach: Let's see for n= 4, then numbers will come from 1 to 16(n*n) in the matrix. As we need to insert numbers in spiral order so here we need 4 things to check, first and last column and top and bottom row. The following four steps we need to do: First, we need to insert numbers in the top row. Our loop will go from the left column to the right then will increase the top row by one and now the top is our second row. Now we are inserting the numbers in the right column, will start the loop from top to bottom, and then decrease the value of the right ...
Read more

Shell Script to Display the digits which are at odd positions in a given 5-digit number - The Coding Shala

Home >> Scripting >> Odd position digits Shell Script to Display the digits which are at odd positions in a given 5-digit number Display the digits which are at odd positions in a given 5-digit number.   Example: number is 23786 output - 276. Code:  #! / bin / bash echo "enter 5 digit number" read number n= 1 while ((n < = 5 )) do a =`echo $number | cut - c $n` echo - n "$a" n=`expr $n + 2 ` done echo " " Other Posts You May Like Shell script to add two numbers using command line argument Shell script to generate Fibonacci series Shell script to find factorial of a number Shell script to print a number in reverse order Shell script to create a simple calculator Please leave a comment below if you like this post or found some error, it will help me to improve my content.
Read more

First Missing Positive Solution - The Coding Shala

Home >> Interview Prep >> First missing positive  In this post, we will learn how to solve the First Missing Positive problem and will implement its solution in Java. First Missing Positive Problem Given an unsorted integer array nums, find the smallest missing positive integer. You must implement an algorithm that runs in O(n) time and uses constant extra space. Example 1: Input: nums = [1,2,0] Output: 3 Example 2: Input: nums = [3,4,-1,1] Output: 2 First Missing Positive Java Solution Approach 1 Time Complexity: O(n) Space Complexity: O(1) The steps are below to solve this problem: Step 1: The first missing positive number will be in the range of 1 to N+1, where N is the length of the array. So Other than these numbers we can ignore, make this change in the array. Step 2: Now we will take the array elements as the index(their original position), and at the numbers' original position will make the array element negative so later we can check this number ...
Read more