Leetcode 367- Valid Perfect Square solution

techieindoor

2 years ago

Here, this tutorial will help you to understand about Valid Perfect Square solution of leetcode 367 problem with algorithm.

You are given a positive integer number lets say n. You have to return true If number is a perfect square else false.

Don’t use any built-in function such as sqrt.

Example 1:

Input: num = 4
Output: true

Input: num = 21
Output: false

Input: num = 64
Output: true

Algorithm for Valid Perfect Square problem:

If input number is 1 then return true
If input number is greater than 1:
- Use start number as 2 and end number as (num / 2). Similar to binary search.
- Get the middle value of start and end by ((start + end) / 2)).
  - Check if mid * mid is equal to number. If it is equal then return true
  - If mid * mid is less than number then update start value to mid + 1
  - If mid * mid is greater than number then update end value to mid - 1
If number is not a perfect square, then return false.

Valid Perfect Square solution code in C++

Code 1:

#include <iostream>

using namespace std;

bool isPerfectSquare(int num) {
        if(num == 1) {
            return true;
        }
        
        int start = 2;
        int end = num / 2;
        long long int mid;
        
        while(start <= end) {
            mid = (start + end) / 2;
            
            if(mid * mid == num) {
                return true;
            } else if(mid * mid < num) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return false;
}

int main() {
    cout<<isPerfectSquare(5);
}

Code 2:

#include <iostream>

using namespace std;

bool isPerfectSquare(int num) {
        int i=1;

        while(num>0) {
            //Subtracting odd number from num and updating num
            num -= i;
            
            // Updating i to the next odd number
            i +=2;
            
            if(!num) {
                return true;
            }
        }
        return false;
    }

int main() {
    cout<<isPerfectSquare(64);
}

Valid Perfect Square solution code in Go

package main

import "fmt"

func isPerfectSquare(num int) bool {
    if num == 1 {
        return true
    }
    start := 2
    end := num / 2
    
    for start <= end {
        mid := (start + end) / 2
        
        if mid * mid == num {
            return true
        } else if mid * mid < num {
            start = mid + 1
        } else {
            end = mid - 1
        }
    }
    return false;
}

func main() {
    fmt.Println(isPerfectSquare(144))
}

To learn more about C++ pls refer given below link:

https://www.techieindoor.com/category/golang/

C++ –

References:

https://www.cplusplus.com/