Press "Enter" to skip to content

Huahua's Tech Road

花花酱 LeetCode 2176. Count Equal and Divisible Pairs in an Array

By zxi on March 4, 2022

Given a 0-indexed integer array nums of length n and an integer k, return the number of pairs(i, j)where0 <= i < j < n, such thatnums[i] == nums[j]and(i * j)is divisible byk.

Example 1:

Input: nums = [3,1,2,2,2,1,3], k = 2
Output: 4
Explanation:
There are 4 pairs that meet all the requirements:
- nums[0] == nums[6], and 0 * 6 == 0, which is divisible by 2.
- nums[2] == nums[3], and 2 * 3 == 6, which is divisible by 2.
- nums[2] == nums[4], and 2 * 4 == 8, which is divisible by 2.
- nums[3] == nums[4], and 3 * 4 == 12, which is divisible by 2.

Example 2:

Input: nums = [1,2,3,4], k = 1
Output: 0
Explanation: Since no value in nums is repeated, there are no pairs (i,j) that meet all the requirements.

Constraints:

  • 1 <= nums.length <= 100
  • 1 <= nums[i], k <= 100

Solution: Brute Force

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

C++

花花酱 LeetCode 2183. Count Array Pairs Divisible by K

By zxi on March 4, 2022

Given a 0-indexed integer array nums of length n and an integer k, return the number of pairs (i, j) such that:

  • 0 <= i < j <= n - 1 and
  • nums[i] * nums[j] is divisible by k.

Example 1:

Input: nums = [1,2,3,4,5], k = 2
Output: 7
Explanation: 
The 7 pairs of indices whose corresponding products are divisible by 2 are
(0, 1), (0, 3), (1, 2), (1, 3), (1, 4), (2, 3), and (3, 4).
Their products are 2, 4, 6, 8, 10, 12, and 20 respectively.
Other pairs such as (0, 2) and (2, 4) have products 3 and 15 respectively, which are not divisible by 2.

Example 2:

Input: nums = [1,2,3,4], k = 5
Output: 0
Explanation: There does not exist any pair of indices whose corresponding product is divisible by 5.

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i], k <= 105

Solution: Math

a * b % k == 0 <=> gcd(a, k) * gcd(b, k) == 0

Use a counter of gcd(x, k) so far to compute the number of pairs.

Time complexity: O(n*f), where f is the number of gcds, f <= 128 for x <= 1e5
Space complexity: O(f)

C++

花花酱 LeetCode 2182. Construct String With Repeat Limit

By zxi on March 3, 2022

You are given a string s and an integer repeatLimit. Construct a new string repeatLimitedString using the characters of s such that no letter appears more than repeatLimit times in a row. You do not have to use all characters from s.

Return the lexicographically largest repeatLimitedString possible.

A string a is lexicographically larger than a string b if in the first position where a and b differ, string a has a letter that appears later in the alphabet than the corresponding letter in b. If the first min(a.length, b.length) characters do not differ, then the longer string is the lexicographically larger one.

Example 1:

Input: s = "cczazcc", repeatLimit = 3
Output: "zzcccac"
Explanation: We use all of the characters from s to construct the repeatLimitedString "zzcccac".
The letter 'a' appears at most 1 time in a row.
The letter 'c' appears at most 3 times in a row.
The letter 'z' appears at most 2 times in a row.
Hence, no letter appears more than repeatLimit times in a row and the string is a valid repeatLimitedString.
The string is the lexicographically largest repeatLimitedString possible so we return "zzcccac".
Note that the string "zzcccca" is lexicographically larger but the letter 'c' appears more than 3 times in a row, so it is not a valid repeatLimitedString.

Example 2:

Input: s = "aababab", repeatLimit = 2
Output: "bbabaa"
Explanation: We use only some of the characters from s to construct the repeatLimitedString "bbabaa". 
The letter 'a' appears at most 2 times in a row.
The letter 'b' appears at most 2 times in a row.
Hence, no letter appears more than repeatLimit times in a row and the string is a valid repeatLimitedString.
The string is the lexicographically largest repeatLimitedString possible so we return "bbabaa".
Note that the string "bbabaaa" is lexicographically larger but the letter 'a' appears more than 2 times in a row, so it is not a valid repeatLimitedString.

Constraints:

  • 1 <= repeatLimit <= s.length <= 105
  • s consists of lowercase English letters.

Solution: Greedy

Adding one letter at a time, find the largest one that can be used.

Time complexity: O(26*n)
Space complexity: O(1)

C++

花花酱 LeetCode 2181. Merge Nodes in Between Zeros

By zxi on March 2, 2022

You are given the head of a linked list, which contains a series of integers separated by 0‘s. The beginning and end of the linked list will have Node.val == 0.

For every two consecutive 0‘s, merge all the nodes lying in between them into a single node whose value is the sum of all the merged nodes. The modified list should not contain any 0‘s.

Return the head of the modified linked list.

Example 1:

Input: head = [0,3,1,0,4,5,2,0]
Output: [4,11]
Explanation: 
The above figure represents the given linked list. The modified list contains
- The sum of the nodes marked in green: 3 + 1 = 4.
- The sum of the nodes marked in red: 4 + 5 + 2 = 11.

Example 2:

Input: head = [0,1,0,3,0,2,2,0]
Output: [1,3,4]
Explanation: 
The above figure represents the given linked list. The modified list contains
- The sum of the nodes marked in green: 1 = 1.
- The sum of the nodes marked in red: 3 = 3.
- The sum of the nodes marked in yellow: 2 + 2 = 4.

Constraints:

  • The number of nodes in the list is in the range [3, 2 * 105].
  • 0 <= Node.val <= 1000
  • There are no two consecutive nodes with Node.val == 0.
  • The beginning and end of the linked list have Node.val == 0.

Solution: List

Skip the first zero, replace every zero node with the sum of values of its previous nodes.

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

C++

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