package com.geth1b.coding.skills.lc;

/**
 *  [Reference URL]:  https://leetcode.com/problems/valid-perfect-square/
 *      [Algorithm]:  Binary Search
 * [Data Structure]:  #TODO
 *      [Time BigO]:  O(logn)
 *     [Space BigO]:  O(1)
 *
 * @author geth1b
 */
public class _367_ValidPerfectSquare {

  // Binary search - input num is > 0 per question requirement
  // 1) Must mid*mid to check equal (=); otherwise 2 = 5/2
  // 2) Must mid vs num/mid to check < or > to avoid overflow; e.g. num = 2,147,483,647
  //
  // O(logn) time
  // O(1) space
  public boolean isPerfectSquare(int num) {
    for (int L = 1, R = num; L <= R;) { // R could be up to num; e.g. num = 1
      int mid = (L + R) / 2;
      if (mid * mid == num) { // must use *; e.g. 2 == 5/2; overflow is fine and won't equal
        return true;
      } else if (mid < num / mid) {
        L = mid + 1;
      } else {
        R = mid - 1;
      }
    }
    return false;
  }  
  
}
