digits Archives - Huahua's Tech Road

花花酱 LeetCode 258. Add Digits

By zxi on March 9, 2020

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?

Solution 1: Simulation

Time complexity: O(logn)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int addDigits(int num) {

int n = num;

while (n >= 10) {

int t = n;

n = 0;

while (t) {

n += t % 10;

t /= 10;

}

return n;

}

};

Solution 2: Math

https://en.wikipedia.org/wiki/Digital_root#Congruence_formula

Digit root = num % 9 if num % 9 != 0 else min(num, 9) e.g. 0 or 9

Time complexity: O(1)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int addDigits(int num) {

return num % 9 ? num % 9 : min(num, 9);

}

};

花花酱 LeetCode 1317. Convert Integer to the Sum of Two No-Zero Integers

By zxi on January 13, 2020

Given an integer n. No-Zero integer is a positive integer which doesn’t contain any 0 in its decimal representation.

Return a list of two integers [A, B] where:

A and B are No-Zero integers.
A + B = n

It’s guarateed that there is at least one valid solution. If there are many valid solutions you can return any of them.

Example 1:

Input: n = 2

Output: [1,1]

Explanation: A = 1, B = 1. A + B = n and both A and B don't contain any 0 in their decimal representation.

Example 2:

1 2	<strong>Input:</strong> n = 11 <strong>Output:</strong> [2,9]

Example 3:

1 2	<strong>Input:</strong> n = 10000 <strong>Output:</strong> [1,9999]

Example 4:

1 2	<strong>Input:</strong> n = 69 <strong>Output:</strong> [1,68]

Example 5:

1 2	<strong>Input:</strong> n = 1010 <strong>Output:</strong> [11,999]

Constraints:

2 <= n <= 10^4

Solution: Brute Force

Time complexity: O(nlogn)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

vector<int> getNoZeroIntegers(int n) {

auto valid = [](int x) {

if (!x) return false;

while (x) {

if (x % 10 == 0) return false;

x /= 10;

}

return true;

};

for (int i = 1; i <= n / 2; ++i)

if (valid(i) && valid(n - i))

return {i, n - i};

return {};

}

};

花花酱 LeetCode 1295. Find Numbers with Even Number of Digits

By zxi on December 26, 2019

Given an array nums of integers, return how many of them contain an even number of digits.

Example 1:

Input: nums = [12,345,2,6,7896]
Output: 2
Explanation: 
12 contains 2 digits (even number of digits). 
345 contains 3 digits (odd number of digits). 
2 contains 1 digit (odd number of digits). 
6 contains 1 digit (odd number of digits). 
7896 contains 4 digits (even number of digits). 
Therefore only 12 and 7896 contain an even number of digits.

Example 2:

Input: nums = [555,901,482,1771]
Output: 1 
Explanation: 
Only 1771 contains an even number of digits.

Constraints:

1 <= nums.length <= 500
1 <= nums[i] <= 10^5

Solution: Math

Time complexity: O(n * log(max(num)))
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int findNumbers(vector<int>& nums) {

return count_if(begin(nums), end(nums), [](int num) {

int d = 0;

do { ++d; } while (num /= 10);

return d % 2 == 0;

});

}

};

Python3

# Author: Huahua

class Solution:

def findNumbers(self, nums: List[int]) -> int:

return sum([len(str(x)) % 2 == 0 for x in nums])

Posts tagged as “digits”

花花酱 LeetCode 258. Add Digits

Solution 1: Simulation

C++

Solution 2: Math

C++

花花酱 LeetCode 1317. Convert Integer to the Sum of Two No-Zero Integers

Solution: Brute Force

C++

花花酱 LeetCode 1295. Find Numbers with Even Number of Digits

Solution: Math

C++

Python3