2 Ways To Solve Add Digit Problem in C++
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.
Approach 1: Linear approach
int addDigit(int num) { int digitalRoot = 0; while(num) { digitalRoot += num % 10; num /= 10; if(num == 0 && digitalRoot > 9) { num = digitalRoot; digitalRoot = 0; } } return digitalRoot; }
Complexity Analysis
- Time complexity : O(n).
- Space complexity : O(1).
Recursive solution
int addDigit(int num) { if(num < 10) return num; int digitalRoot = 0; while(num) { digitalRoot += (num % 10); num /= 10; } return addDigit(digitalRoot); }
Approach 2: Mathematical - Digital Root
Digital root is a school math concept.
The digital root is the difference between the number and the largest multiple of 9 less than the number itself.
Digital Root of 1000 is 1. Largest multiple of 9 is less then 1000 = 9 * 11 = 999 So digital root = 1000 - 999 = 1; Digital Root of 38 is 2; Largest multiple of 9 is less then 38 = 9 * 4 = 36 So digital root = 38 - 36 = 2;
Actually if we divide any number with 9 then reminder will be the digital root.
Digital Root of 1000 is 1. by 1000 % 9 = 1 Digital Root of 38 is 2. by 38 % 9 = 2
But what if the number is itself multiple of 9 what will happened then? Simple 9 will be the digital root of that number then.
int addDigit(int num) { if(num == 0) return 0; if(num % 9 == 0) return 9; return num % 9; }
We can reduce it to one line solution 😙
int addDigit(int num) { return 1 + (num - 1) % 9; }
Complexity Analysis
- Time complexity : O(1).
- Space complexity : O(1).
Comments
Leave a comment
You are not LoggedIn but you can comment as an anonymous user which requires manual approval. For better experience please Login.