LeetCode - Math

Posted on | In ,

Record the Math topic algorithm problems.

0007. Reverse Integer

Given a 32-bit signed integer, reverse digits of an integer.
Example 1:
Input: 123
Output: 321
Example 2:
Input: -123
Output: -321
Example 3:
Input: 120
Output: 21
Note:
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const reverse = (x) => {
    let i = 1;
    let array = String(x).split('').reverse()
    if (x < 0) {
        i = -1;
        array.pop();
    }
    let result = Number(array.join(''))
    if (result > Math.pow(2, 31) - 1) {
        return 0
    } else {
        return  result * i
    }
}

Runtime: 72 ms
Memory Usage: 36.1 MB

0013. Roman to Integer

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:
I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.
Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.
Example 1:
Input: “III”
Output: 3
Example 2:
Input: “IV”
Output: 4
Example 3:
Input: “IX”
Output: 9
Example 4:
Input: “LVIII”
Output: 58
Explanation: L = 50, V= 5, III = 3.
Example 5:
Input: “MCMXCIV”
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

solution 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const romanToInt = (s) =>{
    if (!s || s.length === 0) {
        return 0;
    }
    let str = {"I":1,"V":5,"X":10,"L":50,"C":100,"D":500,"M":1000};
    let result = 0;
    if(s.indexOf("IV")!== -1) result -= 2;
    if(s.indexOf("IX")!== -1) result -= 2;
    if(s.indexOf("XL")!== -1) result -= 20;
    if(s.indexOf("XC")!== -1) result -= 20;
    if(s.indexOf("CD")!== -1) result -= 200;
    if(s.indexOf("CM")!== -1) result -= 200;
    for(let i = 0; i < s.length; i++){
       result += str[s[i]];
    }
    return result;
};

Runtime: 136 ms
Memory Usage: 39 MB

solution 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const romanToInt = (s) =>{
    if (!s || s.length === 0) {
        return 0;
    }
    const map = new Map([['I', 1], ['V', 5], ['X', 10], ['L', 50], ['C', 100], ['D', 500], ['M', 1000]]);
    let i = s.length - 1;
    let result = map.get(s[i]);
    for (i; i > 0; i--) {
        const curr = map.get(s[i]);
        const prev = map.get(s[i - 1]);
        if (prev >= curr) {
          result += prev;
        } else {
          result -= prev;
        }
    }

    return result;
};

Runtime: 152 ms
Memory Usage: 41.6 MB

0069. Sqrt(x)

Implement int sqrt(int x).
Compute and return the square root of x, where x is guaranteed to be a non-negative integer.
Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
Example 1:
Input: 4
Output: 2
Example 2:
Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842…, and since
the decimal part is truncated, 2 is returned.

solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const mySqrt = (x) => {
    let left = 1;
    let right = Math.floor(x / 2) + 1;
    let mid;

    while (left <= right) {
        mid = Math.floor((left + right) / 2);

        if (mid * mid > x) {
          right = mid - 1;
        } else if (mid * mid < x) {
          left = mid + 1;
        } else {
          return mid;
        }
    }

    return right;
};

Runtime: 80 ms
Memory Usage: 35.7 MB

0171. Excel Sheet Column Number

Given a column title as appear in an Excel sheet, return its corresponding column number.
For example:
A -> 1
B -> 2
C -> 3
…
Z -> 26
AA -> 27
AB -> 28
…
Example 1:
Input: “A”
Output: 1
Example 2:
Input: “AB”
Output: 28
Example 3:
Input: “ZY”
Output: 701

solution 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const titleToNumber = (s) => {
    const charCodeBase = 'A'.charCodeAt(0) - 1;
    const n = s.length;
    let number = 0;

    /*
     * Think of it as base 26. For example,
     * Column number of "AB" = 1 * 26^1 + 2 * 26^0
     */
    for (let i = 0; i < n; i++)
        number += (s.charCodeAt(i) - charCodeBase) * Math.pow(26, n-i-1);

    return number;
};

Runtime: 84 ms
Memory Usage: 34.8 MB

0172. Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!.
Example 1:
Input: 3
Output: 0
Explanation: 3! = 6, no trailing zero.
Example 2:
Input: 5
Output: 1
Explanation: 5! = 120, one trailing zero.
Note: Your solution should be in logarithmic time complexity.

solution:

We can simplify the answer to the Factorial Trailing Zeroes question to the following:
(n / 5) + (n / 5^2) + (n / 5^3)… (n / 5^x)
We continue until 5^x is greater than n.

1
2
3
4
5
6
7
const trailingZeroes = function(n) {
    let numZeroes = 0;
    for (let i = 5; i <= n; i *= 5) {
        numZeroes += Math.floor(n / i);
    }
    return numZeroes;
};

Runtime: 44 ms
Memory Usage: 34 MB

0202. Happy Number

Write an algorithm to determine if a number is “happy”.
A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.
Example:
Input: 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

solution 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const isHappy = (n) => {
    if (n < 1) {
        return false;
    }
    let set = new Set();
    while (!set.has(n)) {
        set.add(n);
        let s = n.toString();
        n = 0;
        for (let i = 0; i < s.length; ++i) {
            n += Math.pow(parseInt(s[i]), 2);
        }
        if (n === 1) {
            return true;
        }
    }

    return false;
};

Runtime: 64 ms
Memory Usage: 35.6 MB

solution 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const isHappy = (n) => {
    if (n < 1) {
        return false;
    }
    const squares = {'0':0, '1':1, '2':4, '3':9, '4':16, '5':25, '6':36, '7':49, '8':64, '9':81}
    let set = new Set();
    while (!set.has(n)) {
        set.add(n);
        let s = n.toString();
        n = 0;
        for (let i = 0; i < s.length; ++i) {
            n += squares[s[i]];
        }
        if (n === 1) {
            return true;
        }
    }

    return false;
};

Runtime: 56 ms
Memory Usage: 35.9 MB

0204. Count Primes

Count the number of prime numbers less than a non-negative number, n.
Example:
Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const countPrimes = (n) => {
    if (n < 2) {
        return 0;
    }
    let arr = new Array(n).fill(true);
    const m = Math.sqrt(n);
    arr[0] = false;
    arr[1] = false;
    for(let i = 2; i < m; i++){
        if(arr[i]){
            for(let j = i; j * i < n; j++){
                arr[i * j] = false;
            }
        }
    }
    return arr.filter( n => n === true).length;
};

Runtime: 120 ms
Memory Usage: 63.4 MB

0279. Perfect Squares

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.
Example 1:
Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.
Example 2:
Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

solution:

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
const numSquares = (n) => {
    let isSquare = x=> Math.floor(Math.sqrt(x))**2 === x
    if (isSquare(n)) {
        return 1;
    }
    // that would be the fact that its equal to itself
    // Legendre's three square theorem: A natural number n can be represented as
	// the sum of three squares of integers if and only if : n!= 4^x ( 8*m+7)
    while (n % 4 === 0) {
        n /= 4;
    }
    if (n % 8 === 7) {
        return 4;
    }
    // if n%8!==7 that means that my number can be written
	// as a sum  at of at most 3 squares
	// , otherwise the answer is definitely 4 because of Lagrange's theorem.
    // ok, we ruled out the possibility of result 4
    // there are only 2 results remaining, 2 and 3

    // Manually checking for result 2
    for (let i = 0; i <= n ; i++) {
        // if x=n-i*i   and x is a valid square then OBVIOUSLY
        // n=i^2 +sqrt(x)^2  ,so n is a square of two numbers
        if(isSquare(n - i * i)) {
            return 2;
        }
    }
    // otherwise
    return 3;
};

Runtime: 56 ms
Memory Usage: 35.1 MB

0326. Power of Three

Given an integer, write a function to determine if it is a power of three.
Example 1:
Input: 27
Output: true
Example 2:
Input: 0
Output: false
Example 3:
Input: 9
Output: true
Example 4:
Input: 45
Output: false
Follow up:
Could you do it without using any loop / recursion?

solution 1:

1
2
3
const isPowerOfThree = (n) => {
    return n.toString(3).split("").reduce((prev,curr) => parseInt(prev) + parseInt(curr)) == 1;
};

Runtime: 252 ms
Memory Usage: 48.9 MB

solution 2:

1
2
3
const isPowerOfThree = (n) => {
    return /^10*$/.test(n.toString(3));
};

Runtime: 244 ms
Memory Usage: 46.8 MB

solution 3:

1
2
3
const isPowerOfThree = (n) => {
    return Number.isInteger(Math.log10(n) / Math.log10(3))
};

Runtime: 228 ms
Memory Usage: 47.8 MB