Add Digits

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

For example:

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

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


Solution:

consider O(1) The algorithm of , Start with the simplest numbers :

0 - 9 No doubt they all correspond to the return of 0 - 9 That's it .

Next ,

10 return 1

11 return 2

12 return 3

13 return 4

……

18 return 9

19 return 1

……

The law is about to come out , Because eventually all the numbers will be Mapping to 0 - 9 this 10 On a digital , That's why I began to consider whether there are some essential laws in such mapping , From the above, we can find that the law is that the number increases with the size of the number itself , The number mapped to is actually increasing , But this increase is actually based on 9 For the mould , For this problem, we only care about the remainder after taking the module, but not about the number itself “ model 9” 了 .

One thing to note is that :

0 It's special here , Only 0 The number itself maps to 0 , There are no more numbers mapped to 0, It needs to be dealt with separately .

So actually We are will except 0 Numbers outside mapping To 1-9 this Nine On a digital , If you think about it, the result should be (num-1) % 9 + 1.

The code is as follows :

 class Solution:
# @param {integer} num
# @return {integer}
def addDigits(self, num):
if num == 0:
return 0
else:
return (num-1) % 9 + 1

【LeetCode】Add Digits More articles about

  1. 【02_258】Add Digits

    Add Digits Total Accepted: 49702 Total Submissions: 104483 Difficulty: Easy Given a non-negative int ...

  2. 【leetcode】Add Two Numbers

    Title Description : You are given two linked lists representing two non-negative numbers. The digits are stored in ...

  3. 【 Answer key 】【 Linked list 】【Leetcode】Add Two Numbers

    You are given two linked lists representing two non-negative numbers. The digits are stored in rever ...

  4. 【leetcode】Add Two Numbers(middle) *

    You are given two linked lists representing two non-negative numbers. The digits are stored in rever ...

  5. 【leetcode】 Add Two Numbers

    You are given two linked lists representing two non-negative numbers. The digits are stored in rever ...

  6. 【LeetCode】Add Two Numbers( Addition of two numbers )

    The question is LeetCode Li di 2 Problem . Subject requirements : Two are given.   Non empty   The list of is used to represent two non negative integers . among , Their respective digits are based on   The reverse   Stored in , And each of their nodes can only store   a   Numbers . If , We will ...

  7. 【LeetCode】Reverse digits of an integer

    Reverse digits of an integer. Example1: x = 123, return 321Example2: x = -123, return -321 Have you ...

  8. 【leetcode】Add Binary

    A brief introduction to the topic : Given two binary strings, return their sum (also a binary string). For example, a = "11&q ...

  9. 【LeetCode】 mathematics ( common 106 topic )

    [2]Add Two Numbers (2018 year 12 month 23 Japan ,review) High precision addition of linked list . Answer key : Special topic of linked list :https://www.cnblogs.com/zhangwanying/p/979 ...

Random recommendation

  1. QT Medium C/S Communication problems : About the server side readyread() The signal doesn't transmit

    stay windows Next use QT test C/S When communicating , The server cannot read the data sent by the client . Later set breakpoints to check for errors , Found to be readyread The reason why the signal doesn't trigger . Later, I wrote on the client socket A sentence was added at the end so ...

  2. asp.net mvc Custom authentication

    1. Define identity entity objects /// <summary> /// Website user entity objects /// </summary> public class DDTPrincipal : IPrinci ...

  3. Late Android Of Camera Development summary

    This is a project written a long time ago , But I haven't summed it up yet . Just in the time of looking for a job to summarize what I have done , What I learned . Write Android When applying custom camera , The first thing to know is Camera Dimensions that development must know , Otherwise, when debugging , ...

  4. Linux Under the system tomcat journal

    stay Linux Under the system ,tomcat journal catalina.out It's not like window Under the system , Rewrite backup by date , So in Linux The system will cause the log file to be too large , This paper introduces the use of  cronolog The tool carries on as in w ...

  5. hdu 1528 Card Game Cheater ( Bipartite map matching )

    subject : Click to open the link The question : A card game for two , People with big cards score . Big card :2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < T < J < ...

  6. MySQL Adopt Xtrabackup Backup the whole database

    1,xtrabackup Brief introduction About database backup and backup tools . Refer to :http://blog.itpub.net/26230597/viewspace-1460065/, Let's introduce xtrabackup has ...

  7. Maven Use local jar package ( Two ways )

    Some projects will use some Maven What's not in the library jar package , We need to introduce it ourselves There are two ways to do this : The first way , stay pom Use the local path when referring to a file : First turn on the jar Package into project : And then in pom Introduce in the file : &l ...

  8. Idea Tomcat Servlet Path configuration problem

    The virtual path problem is not clear , For a long time . in general :login.html(action) and loginServlet(@webServlet) The virtual path of is one /day14. At the same time, both of them are in browser access , Must be ...

  9. [AHOI2013] Homework

    [AHOI2013] Homework The main idea of the topic : Given a length of \(n(n\le10^5)\) Sequence of numbers \(A(1\le A_i\le n)\).\(m(m\le10^6)\) Time to ask , The interval of each inquiry \([l,r]\) Inside ...

  10. ELK Study notes Logstash Detailed explanation

    0x00 Logstash summary The official introduction :Logstash is an open source data collection engine with real-time pipelining cap ...