base10 Archives - Huahua's Tech Road

花花酱 LeetCode 2180. Count Integers With Even Digit Sum

By zxi on February 28, 2022

Given a positive integer num, return the number of positive integers less than or equal to num whose digit sums are even.

The digit sum of a positive integer is the sum of all its digits.

Example 1:

Input: num = 4
Output: 2
Explanation:
The only integers less than or equal to 4 whose digit sums are even are 2 and 4.

Example 2:

Input: num = 30
Output: 14
Explanation:
The 14 integers less than or equal to 30 whose digit sums are even are
2, 4, 6, 8, 11, 13, 15, 17, 19, 20, 22, 24, 26, and 28.

Constraints:

1 <= num <= 1000

Solution: Brute Force

Use std::to_string to convert an integer to string.

Time complexity: O(nlgn)
Space complexity: O(lgn)

C++

// Author: Huahua

class Solution {

public:

int countEven(int num) {

int ans = 0;

for (int i = 1; i <= num; ++i) {

int sum = 0;

for (char c : to_string(i))

sum += (c - '0');

if (sum % 2 == 0) ++ans;

}

return ans;

}

};

花花酱 LeetCode 1945. Sum of Digits of String After Convert

By zxi on December 31, 2021

You are given a string s consisting of lowercase English letters, and an integer k.

First, convert s into an integer by replacing each letter with its position in the alphabet (i.e., replace 'a' with 1, 'b' with 2, …, 'z' with 26). Then, transform the integer by replacing it with the sum of its digits. Repeat the transform operation k times in total.

For example, if s = "zbax" and k = 2, then the resulting integer would be 8 by the following operations:

Convert: "zbax" ➝ "(26)(2)(1)(24)" ➝ "262124" ➝ 262124
Transform #1: 262124 ➝ 2 + 6 + 2 + 1 + 2 + 4 ➝ 17
Transform #2: 17 ➝ 1 + 7 ➝ 8

Return the resulting integer after performing the operations described above.

Example 1:

Input: s = "iiii", k = 1
Output: 36
Explanation: The operations are as follows:
- Convert: "iiii" ➝ "(9)(9)(9)(9)" ➝ "9999" ➝ 9999
- Transform #1: 9999 ➝ 9 + 9 + 9 + 9 ➝ 36
Thus the resulting integer is 36.

Example 2:

Input: s = "leetcode", k = 2
Output: 6
Explanation: The operations are as follows:
- Convert: "leetcode" ➝ "(12)(5)(5)(20)(3)(15)(4)(5)" ➝ "12552031545" ➝ 12552031545
- Transform #1: 12552031545 ➝ 1 + 2 + 5 + 5 + 2 + 0 + 3 + 1 + 5 + 4 + 5 ➝ 33
- Transform #2: 33 ➝ 3 + 3 ➝ 6
Thus the resulting integer is 6.

Example 3:

Input: s = "zbax", k = 2
Output: 8

Constraints:

1 <= s.length <= 100
1 <= k <= 10
s consists of lowercase English letters.

Solution: Simulation

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

C++

// Author: Huahua

class Solution {

public:

int getLucky(string s, int k) {

int ans = 0;

for (char c : s) {

int n = c - 'a' + 1;

ans += n % 10;

ans += n / 10;

}

while (--k) {

int n = ans;

ans = 0;

while (n) {

ans += n % 10;

n /= 10;

}

return ans;

}

};

花花酱 LeetCode 1742. Maximum Number of Balls in a Box

By zxi on January 30, 2021

You are working in a ball factory where you have n balls numbered from lowLimit up to highLimit inclusive (i.e., n == highLimit - lowLimit + 1), and an infinite number of boxes numbered from 1 to infinity.

Your job at this factory is to put each ball in the box with a number equal to the sum of digits of the ball’s number. For example, the ball number 321 will be put in the box number 3 + 2 + 1 = 6 and the ball number 10 will be put in the box number 1 + 0 = 1.

Given two integers lowLimit and highLimit, return the number of balls in the box with the most balls.

Example 1:

Input: lowLimit = 1, highLimit = 10
Output: 2
Explanation:
Box Number:  1 2 3 4 5 6 7 8 9 10 11 ...
Ball Count:  2 1 1 1 1 1 1 1 1 0  0  ...
Box 1 has the most number of balls with 2 balls.

Example 2:

Input: lowLimit = 5, highLimit = 15
Output: 2
Explanation:
Box Number:  1 2 3 4 5 6 7 8 9 10 11 ...
Ball Count:  1 1 1 1 2 2 1 1 1 0  0  ...
Boxes 5 and 6 have the most number of balls with 2 balls in each.

Example 3:

Input: lowLimit = 19, highLimit = 28
Output: 2
Explanation:
Box Number:  1 2 3 4 5 6 7 8 9 10 11 12 ...
Ball Count:  0 1 1 1 1 1 1 1 1 2  0  0  ...
Box 10 has the most number of balls with 2 balls.

Constraints:

1 <= lowLimit <= highLimit <= 10⁵

Solution: Hashtable and base-10

Max sum will be 9+9+9+9+9 = 45

Time complexity: O((hi-lo) * log(hi))
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int countBalls(int lowLimit, int highLimit) {

vector<int> balls(46);

int ans = 0;

for (int i = lowLimit; i <= highLimit; ++i) {

int n = i;

int box = 0;

while (n) { box += n % 10; n /= 10; }

ans = max(ans, ++balls[box]);

}

return ans;

}

};

Python3

# Author: Huahua

class Solution:

def countBalls(self, lowLimit: int, highLimit: int) -> int:

balls = defaultdict(int)

ans = 0

for x in range(lowLimit, highLimit + 1):

s = sum(int(d) for d in str(x))

balls[s] += 1

ans = max(ans, balls[s])

return ans

Posts tagged as “base10”

花花酱 LeetCode 2180. Count Integers With Even Digit Sum

Solution: Brute Force

C++

花花酱 LeetCode 1945. Sum of Digits of String After Convert

Solution: Simulation

C++

花花酱 LeetCode 1742. Maximum Number of Balls in a Box

Solution: Hashtable and base-10

C++

Python3