leetCodeInt.java

// Problem 69. Sqrt(x)
//Link: https://leetcode.com/problems/sqrtx/submissions/
// Solution: Binary seearch
// Time: O(logn), Space: O(1)
class Solution {
    public int mySqrt(int x) {
        if (x < 2) { return x; }
        
        long left = 0;
        long right = x / 2 + 1;
        
        while (left + 1 < right) {
            long mid = (right - left) / 2 + left;
            
            if (mid * mid > x) {
                right = mid;
            } else if (mid * mid < x) {
                left = mid;
            } else {
                return (int)mid;
            }
        }
        
        if (right * right == x) {
            return (int)right;
        }
        return (int)left;
    }
}



/****************************************************************/
// Problem 70. Climbing Stairs
// Link: https://leetcode.com/problems/climbing-stairs/
// Solution 1: Using fibonacci sequence
// Time: O(n), Space: O(1)
public int climbStairs(int n) {
    if (n == 1) { return n; }

    int first = 1;
    int second = 1;
    for (int i = 2; i <= n; i++) {
        int third = first + second;
        first = second;
        second = third;
    }

    return second;
}