Menu Close

Leetcode 367- Valid Perfect Square solution

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/

References:

https://www.cplusplus.com/

Posted in C++, golang program, Leetcode

Leave a Reply

Your email address will not be published. Required fields are marked *