Posts tagged as “Easy”

Given an integer num, repeatedly add all its digits until the result has only one digit, and return it.

Example 1:

Input: num = 38
Output: 2
Explanation: The process is
38 --> 3 + 8 --> 11
11 --> 1 + 1 --> 2 
Since 2 has only one digit, return it.

Example 2:

Input: num = 0
Output: 0

Constraints:

• 0 <= num <= 231 - 1

Idea 1:

recursive

Solution 1:

/**
 * @param {number} num
 * @return {number}
 */
var addDigits = function(num) {
    let nums = num.toString().split("");
    let sumOfNums = sum(nums);
        
    // base case:
    if (sumOfNums  < 10) return sumOfNums; 
    return addDigits(sumOfNums);
};

function sum(arr) {
    return arr.reduce((a, b) => parseInt(a) + parseInt(b), 0);
}

Idea 2:

mathematics algorithms in O(1) runtime

Solution 2:

/**
 * @param {number} num
 * @return {number}
 */
var addDigits = function(num) {
    return num % 9 ? num % 9 : Math.min(num, 9);
};

Given an integer n, return the number of trailing zeroes in n!.

Follow up: Could you write a solution that works in logarithmic time complexity?

Example 1:

Input: n = 3
Output: 0
Explanation: 3! = 6, no trailing zero.

Example 2:

Input: n = 5
Output: 1
Explanation: 5! = 120, one trailing zero.

Example 3:

Input: n = 0
Output: 0

Constraints:

• 0 <= n <= 104

Idea:

All trailing zeros are come from even_num x 5, we have more even_num than 5, so only count factor 5.

4! = 1x2x3x4 = 24, we haven’t encountered any 5 yet, so we don’t have any trailing zero.

5! = 1x2x3x4x5 = 120, we have one trailing zero. either 2×5, or 4×5 can contribute to that zero.

9! = 362880, we only encountered 5 once, so 1 trailing zero as expected.

10! = 3628800, 2 trailing zeros, since we have two numbers that have factor 5, one is 5 and the other is 10 (2×5)

What about 100! then?

100/5 = 20, we have 20 numbers have factor 5: 5, 10, 15, 20, 25, …, 95, 100.

Is the number of trailing zero 20? No, it’s 24, why?

Within that 20 numbers, we have 4 of them: 25 (5×5), 50 (2x5x5), 75 (3x5x5), 100 (4x5x5) that have an extra factor of 5.

So, for a given number n, we are looking how many numbers <=n have factor 5, 5×5, 5x5x5, …

Summing those numbers up we got the answer.

e.g. 1000! has 249 trailing zeros:

1000/5 = 200

1000/25 = 40

1000/125 = 8

1000/625 = 1

200 + 40 + 8 + 1 = 249

Solution:

/**
 * @param {number} n
 * @return {number}
 */
var trailingZeroes = function(n) {
    return n < 5 ? 0 : parseInt(n / 5) + trailingZeroes(parseInt(n / 5));
};

Given an integer x, return true if x is palindrome integer.

An integer is a palindrome when it reads the same backward as forward. For example, 121 is palindrome while 123 is not.

Example 1:

Input: x = 121
Output: true

Example 2:

Input: x = -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:

Input: x = 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Example 4:

Input: x = -101
Output: false

Constraints:

• -231 <= x <= 231 - 1

Solution:

/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function(x) {
    // negative number is not a Palindrome Number
    if (x < 0) return false;
    let y = x;
    let reverse = 0;
    while (y > 0) {
        let lastDigit = y % 10;
        reverse = reverse * 10 + lastDigit;
        y = parseInt(y / 10);
    }
    return reverse === x ;
};

Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-231, 231 - 1], then return 0.

Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

Example 1:

Input: x = 123
Output: 321

Example 2:

Input: x = -123
Output: -321

Example 3:

Input: x = 120
Output: 21

Example 4:

Input: x = 0
Output: 0

Constraints:

• -231 <= x <= 231 - 1

Solution:

/**
 * @param {number} x
 * @return {number}
 */

var reverse = function(x) {
    const str      = "" + Math.abs(x);   // convert absolute value to string
    const reversed = str.split("")       // get array of digit characters
                   .reverse()            // reverse it
                   .join("");            // join into string again;
    const num      = parseInt(reversed); // convert to integer
    const revNum = Math.sign(x) * num;   // multiple the sign
    // if out of range return 0
    if (revNum < Math.pow(-2, 31) || revNum > Math.pow(2, 31) - 1) return 0;
    return revNum;
}