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
1then returntrue - If input number is greater than
1:- Use
startnumber as2andendnumber as(num / 2). Similar tobinary search. - Get the
middlevalue ofstartandendby((start + end) / 2)).- Check if
mid * midis equal tonumber. If it is equal then returntrue - If
mid * midis less thannumberthen updatestartvalue tomid + 1 - If
mid * midis greater than number then updateendvalue tomid - 1
- Check if
- Use
- If
numberis not a perfect square, then returnfalse.
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://techieindoor.com/category/golang/
References: