LeetCode 258

Add Digits

문제 출처

문제

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

Example:

Input: 38
Output: 2
Explanation: The process is like: 3 + 8 = 11, 1 + 1 = 2.
             Since 2 has only one digit, return it.
Follow up:
Could you do it without any loop/recursion in O(1) runtime?

나의 코드

O(N * M) : 그리 효율적이지 못하다. Follow up 요구 사항인 O(1) 에는 한참 못 미치는 코드이다.

/**
 * @param {number} num
 * @return {number}
 */
var addDigits = function (num) {
  if (num < 10) return num;

  const array = num.toString(10).split("");

  const result = array.reduce((acc, cur) => {
    return acc + Number(cur);
  }, 0);

  return addDigits(result);
};

참고 코드

var addDigits = function (num) {
  if (isNaN(num) || num === 0) return 0;
  if (num < 10) return num;
  return num % 9 === 0 ? 9 : num % 9;
};

배운점

  • O(1) 코드를 짜는 법
    참고 코드 작성자에 따르면 O(1) 코드는 주로 수학을 통해 해결할 수 있다고 한다.
    여러 test input 을 넣어보며 수학적 규칙을 찾아야 한다.
    실제로 위 코드도 간단한 수학 규칙으로 해결했다.