1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
//! Valid Perfect Square [leetcode: valid_perfect_square](https://leetcode.com/problems/valid-perfect-square/) //! //! 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 //! Output: true //! ``` //! //! **Example 2:** //! ``` //! Input: 14 //! Output: false //! ``` //! /// # Solutions /// /// # Approach 1: Binary Search /// /// * Time complexity: log(n) /// /// * Space complexity: log(n) /// /// * Runtime: 0 ms /// * Memory: 2.4 MB /// /// ```rust /// impl Solution { /// pub fn is_perfect_square(num: i32) -> bool { /// if num == 0 { return false; } /// /// let num = num as usize; /// let mut left = 1 as usize; /// let mut right = num; /// /// while left <= right { /// let mid = (right - left) / 2 as usize + left; /// if mid * mid == num { return true; } /// if mid * mid > num { right = mid - 1 as usize; } else { left = mid + 1 as usize; } /// } /// /// false /// } /// } /// ``` /// pub fn is_perfect_square(num: i32) -> bool { if num == 0 { return false; } let num = num as usize; let mut left = 1 as usize; let mut right = num; while left <= right { let mid = (right - left) / 2 as usize + left; if mid * mid == num { return true; } if mid * mid > num { right = mid - 1 as usize; } else { left = mid + 1 as usize; } } false }