[LintCode] Add Digits

QiShare 发布于2019-08-15 13:42 / 1924人阅读

Problem

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

Example

Given num = 38.
The process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return 2.

Challenge

Could you do it without any loop/recursion in O(1) runtime?

Solution

recursive

public class Solution {
    /*
     * @param num: a non-negative integer
     * @return: one digit
     */
    public int addDigits(int num) {
        // write your code here
        if (num < 10) return num;
        int sum = 0;
        while (num != 0) {
            sum += (num%10);
            num /= 10;
        }
        return addDigits(sum);
    }
}

Non-recursive

public class Solution {
    /*
     * @param num: a non-negative integer
     * @return: one digit
     */
    public int addDigits(int num) {
        // write your code here
        while (num >= 10) {
            String cur = Integer.toString(num);
            int sum = 0;
            for (int i = 0; i < cur.length(); i++) {
                sum += Character.getNumericValue(cur.charAt(i));
            }
            num = sum;
        }
        return num;
    }
}

私有云海外云主机 Digits LintCode LintCode134_LRU digits安装在云服务器

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/68260.html

[LeetCode/LintCode] Plus One

Problem Given a non-negative number represented as an array of digits, plus one to the number. The digits are stored such that the most significant digit is at the head of the list. Example Given [1,2...

sunsmell 2019-08-14 15:17 评论0 收藏0
[LintCode] Big Integer Addition

Problem Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2. Notice The length of both num1 and num2 is < 5100.Both num1 and num2 contains only digits ...

i_garfileo 2019-08-16 10:59 评论0 收藏0
[LintCode] Delete Digits [Greedy]

摘要：题意为取删去个字符后最小的值，仍以返回。所以无论删除个元素之后的元素放入顺序如何，此时栈内元素从底到顶的排列一定是满足条件的最小值。这种情况下，就要从堆栈顶部删除剩下的两个元素和然后，将栈内的元素放入，并将顶部的全部去掉，然后以返回。 Problem Given string A representative a positive integer which has N digits,...

张汉庆 2019-08-14 15:21 评论0 收藏0
[LintCode/LeetCode] Add Two Numbers

Problem You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1s digit is at the head of the list. Write a f...

hedzr 2019-08-14 15:21 评论0 收藏0
[LintCode] Print Numbers by Recursion

摘要：只有当位数时，才打印数字。首先分析边界，应该，然后用存最高位。用函数对进行递归运算，同时更新结果数组。更新的过程归纳一下，首先，计算最高位存入，然后，用到倍的和之前里已经存入的所有的数个循环相加，再存入，更新，计算更高位直到等于 Problem Print numbers from 1 to the largest number with N digits by recursion. ...

kumfo 2019-08-14 15:17 评论0 收藏0