LeetCode: Valid Perfect Square (aka binary search)
https://leetcode.com/problems/valid-perfect-square/, problem statement:
Straightforward binary search from 1 to Int32.MaxValue (2147483647) which gives an O-time of Log(2147483647), also known as 31. Code below:
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;
using System.IO;
namespace LeetCode
{
class Program
{
static void Main(string[] args)
{
Solution sol = new Solution();
Console.WriteLine(sol.IsPerfectSquare(Convert.ToInt32(args[0])));
}
}
public class Solution
{
public bool IsPerfectSquare(int num)
{
if (num < 0) return false;
if (num == 0) return true;
long left = 1;
long right = (long)Int32.MaxValue;
while (left <= right)
{
long mid = (left + right) / 2;
long midSqr = mid * mid;
if (midSqr == num) return true;
else if (midSqr > num) right = mid - 1;
else left = mid + 1;
}
return false;
}
}
}
Given a positive integer num, write a function which 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 Returns: True
Example 2:
Input: 14 Returns: False
Straightforward binary search from 1 to Int32.MaxValue (2147483647) which gives an O-time of Log(2147483647), also known as 31. Code below:
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;
using System.IO;
namespace LeetCode
{
class Program
{
static void Main(string[] args)
{
Solution sol = new Solution();
Console.WriteLine(sol.IsPerfectSquare(Convert.ToInt32(args[0])));
}
}
public class Solution
{
public bool IsPerfectSquare(int num)
{
if (num < 0) return false;
if (num == 0) return true;
long left = 1;
long right = (long)Int32.MaxValue;
while (left <= right)
{
long mid = (left + right) / 2;
long midSqr = mid * mid;
if (midSqr == num) return true;
else if (midSqr > num) right = mid - 1;
else left = mid + 1;
}
return false;
}
}
}
Binary search is a swiss army knife of computer science :) It would be my algorithm of choice for solving this problem if not for the huge impression SICP left in my life and one of its chapters about root finding in particular (https://mitpress.mit.edu/sicp/chapter1/node9.html). Similar to algorithms that use element distribution can beat binary search for checking if an element is present in a sorted array, Newton's method uses a mathematical property of a tangent line to get to the square root faster.
ReplyDeleteIn practice both methods are extremely fast and leetcode reported both solutions taking 0ms. Newton's method involves a more expensive division operator (binary search's division by 2 is super cheap, since it's just a shift to right), so the final performance is most likely very close, but I'll post my solution anyways :)
bool isPerfectSquare(int num) {
long guess = num;
while (guess * guess > num) guess = (guess + num/guess) / 2;
return guess * guess == num;
}
P.S.: problem description says that only positive integers will be used, so your first 2 checks are not necessary. Also the `right` can be initialized with the `num`, since square root of a number can be at most that number :)
Awesome problem!