Posts tagged as “hashtable”

花花酱 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

花花酱 LeetCode 1726. Tuple with Same Product

By zxi on January 17, 2021

Given an array nums of distinct positive integers, return the number of tuples (a, b, c, d) such that a * b = c * d where a, b, c, and d are elements of nums, and a != b != c != d.

Example 1:

Input: nums = [2,3,4,6]
Output: 8
Explanation: There are 8 valid tuples:
(2,6,3,4) , (2,6,4,3) , (6,2,3,4) , (6,2,4,3)
(3,4,2,6) , (4,3,2,6) , (3,4,6,2) , (4,3,6,2)

Example 2:

Input: nums = [1,2,4,5,10]
Output: 16
Explanation: There are 16 valids tuples:
(1,10,2,5) , (1,10,5,2) , (10,1,2,5) , (10,1,5,2)
(2,5,1,10) , (2,5,10,1) , (5,2,1,10) , (5,2,10,1)
(2,10,4,5) , (2,10,5,4) , (10,2,4,5) , (10,2,4,5)
(4,5,2,10) , (4,5,10,2) , (5,4,2,10) , (5,4,10,2)

Example 3:

Input: nums = [2,3,4,6,8,12]
Output: 40

Example 4:

Input: nums = [2,3,5,7]
Output: 0

Constraints:

1 <= nums.length <= 1000
1 <= nums[i] <= 10⁴
All elements in nums are distinct.

Solution: HashTable

Similar idea to 花花酱 LeetCode 1. Two Sum

Use a hashtable to store all the pair product counts.

Enumerate all possible pairs, increase the answer by the same product counts * 8.

Why time 8? C(4,1) * C(1,1) * C(2,1) * C(1,1)

For pair one AxB, A can be placed at any position in a four tuple, B’s position is then fixed. For another pair CxD, C has two positions to choose from, D is fixed.

Time complexity: O(n^2)
Space complexity: O(n^2)

C++

// Author: Huahua

class Solution {

public:

int tupleSameProduct(vector<int>& nums) {

const int n = nums.size();

unordered_map<int, int> m;

int ans = 0;

for (int i = 0; i < n; ++i)

for (int j = 0; j < i; ++j)

ans += 8 * m[nums[i] * nums[j]]++;

return ans;

}

};

花花酱 LeetCode 1711. Count Good Meals

By zxi on January 2, 2021

A good meal is a meal that contains exactly two different food items with a sum of deliciousness equal to a power of two.

You can pick any two different foods to make a good meal.

Given an array of integers deliciousness where deliciousness[i] is the deliciousness of the i^th item of food, return the number of different good meals you can make from this list modulo 10⁹ + 7.

Note that items with different indices are considered different even if they have the same deliciousness value.

Example 1:

Input: deliciousness = [1,3,5,7,9]
Output: 4
Explanation: The good meals are (1,3), (1,7), (3,5) and, (7,9).
Their respective sums are 4, 8, 8, and 16, all of which are powers of 2.

Example 2:

Input: deliciousness = [1,1,1,3,3,3,7]
Output: 15
Explanation: The good meals are (1,1) with 3 ways, (1,3) with 9 ways, and (1,7) with 3 ways.

Constraints:

1 <= deliciousness.length <= 10⁵
0 <= deliciousness[i] <= 2²⁰

Solution: Hashtable

Same idea as LeetCode 1: Two Sum

Use a hashtable to store the occurrences of all the numbers added so far. For a new number x, check all possible 2^i – x. ans += freq[2^i – x] 0 <= i <= 21

Time complexity: O(22n)
Space complexity: O(n)

C++

class Solution {

public:

int countPairs(vector<int>& A) {

constexpr int kMod = 1e9 + 7;

unordered_map<int, int> m;

long ans = 0;

for (int x : A) {

for (int t = 1; t <= 1 << 21; t *= 2) {

auto it = m.find(t - x);

if (it != end(m)) ans += it->second;

}

++m[x];

}

return ans % kMod;

}

};

Python3

class Solution:

def countPairs(self, deliciousness: List[int]) -> int:

sums = [1<<i for i in range(22)]

m = defaultdict(int)

ans = 0

for x in deliciousness:

for t in sums:

if t - x in m: ans += m[t - x]

m[x] += 1

return ans % (10**9 + 7)

花花酱 LeetCode 1684. Count the Number of Consistent Strings

By zxi on December 12, 2020

You are given a string allowed consisting of distinct characters and an array of strings words. A string is consistent if all characters in the string appear in the string allowed.

Return the number of consistent strings in the array words.

Example 1:

Input: allowed = "ab", words = ["ad","bd","aaab","baa","badab"]
Output: 2
Explanation: Strings "aaab" and "baa" are consistent since they only contain characters 'a' and 'b'.

Example 2:

Input: allowed = "abc", words = ["a","b","c","ab","ac","bc","abc"]
Output: 7
Explanation: All strings are consistent.

Example 3:

Input: allowed = "cad", words = ["cc","acd","b","ba","bac","bad","ac","d"]
Output: 4
Explanation: Strings "cc", "acd", "ac", and "d" are consistent.

Constraints:

1 <= words.length <= 10⁴
1 <= allowed.length <=26
1 <= words[i].length <= 10
The characters in allowed are distinct.
words[i] and allowed contain only lowercase English letters.

Solution: Hashtable

Time complexity: O(sum(len(word))
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int countConsistentStrings(string allowed, vector<string>& words) {

vector<int> m(26);

for (char c : allowed) m[c - 'a'] = 1;

int ans = 0;

for (const string& w : words)

ans += all_of(begin(w), end(w), [&m](char c) { return m[c - 'a']; });

return ans;

}

};

Python3

# Author: Huahua

class Solution:

def countConsistentStrings(self, allowed: str, words: List[str]) -> int:

return sum(all(c in allowed for c in w) for w in words)

花花酱 LeetCode 1679. Max Number of K-Sum Pairs

By zxi on December 6, 2020

You are given an integer array nums and an integer k.

In one operation, you can pick two numbers from the array whose sum equals k and remove them from the array.

Return the maximum number of operations you can perform on the array.

Example 1:

Input: nums = [1,2,3,4], k = 5
Output: 2
Explanation: Starting with nums = [1,2,3,4]:
- Remove numbers 1 and 4, then nums = [2,3]
- Remove numbers 2 and 3, then nums = []
There are no more pairs that sum up to 5, hence a total of 2 operations.

Example 2:

Input: nums = [3,1,3,4,3], k = 6
Output: 1
Explanation: Starting with nums = [3,1,3,4,3]:
- Remove the first two 3's, then nums = [1,4,3]
There are no more pairs that sum up to 6, hence a total of 1 operation.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹
1 <= k <= 10⁹

Solution 1: Frequency Map

For each x, check freq[x] and freq[k – x]. Note: there is a special case when x + x == k.

Time complexity: O(n)
Space complexity: O(n)

C++

class Solution {

public:

int maxOperations(vector<int>& nums, int k) {

unordered_map<int, int> m;

int ans = 0;

for (int x : nums) ++m[x];

for (int x : nums) {

if (m[x] < 1 || m[k - x] < 1 + (x + x == k)) continue;

--m[x];

--m[k - x];

++ans;

}

return ans;

}

};

Python3

class Solution:

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

m = defaultdict(int)

ans = 0

for x in nums: m[x] += 1

for x in nums:

if m[x] < 1 or m[k - x] < 1 + (x + x == k): continue

m[x] -= 1

m[k - x] -= 1

ans += 1

return ans

Solution 2: Two Pointers

Sort the number, start from i = 0, j = n – 1, compare s = nums[i] + nums[j] with k and move i, j accordingly.

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

C++

class Solution {

public:

int maxOperations(vector<int>& nums, int k) {

sort(begin(nums), end(nums));

int i = 0, j = nums.size() - 1;

int ans = 0;

while (i < j) {

const int s = nums[i] + nums[j];

if (s == k) {

++ans;

++i; --j;

} else if (s < k) {

++i;

} else {

--j;

}

return ans;

}

};