Posts tagged as “two sum”

花花酱 LeetCode 1814. Count Nice Pairs in an Array

By zxi on April 3, 2021

You are given an array nums that consists of non-negative integers. Let us define rev(x) as the reverse of the non-negative integer x. For example, rev(123) = 321, and rev(120) = 21. A pair of indices (i, j) is nice if it satisfies all of the following conditions:

0 <= i < j < nums.length
nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])

Return the number of nice pairs of indices. Since that number can be too large, return it modulo 10⁹ + 7.

Example 1:

Input: nums = [42,11,1,97]
Output: 2
Explanation: The two pairs are:
 - (0,3) : 42 + rev(97) = 42 + 79 = 121, 97 + rev(42) = 97 + 24 = 121.
 - (1,2) : 11 + rev(1) = 11 + 1 = 12, 1 + rev(11) = 1 + 11 = 12.

Example 2:

Input: nums = [13,10,35,24,76]
Output: 4

Constraints:

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

Solution: Two Sum

Key = x – rev(x)

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

C++

// Author: Huahua

class Solution {

public:

int countNicePairs(vector<int>& nums) {

constexpr int kMod = 1e9 + 7;

unordered_map<int, int> m;

long ans = 0;

for (int x : nums) {

string s = to_string(x);

reverse(begin(s), end(s));

ans += m[x - stoi(s)]++;

}

return ans % kMod;

}

};

花花酱 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 1498. Number of Subsequences That Satisfy the Given Sum Condition

By zxi on June 28, 2020

Given an array of integers nums and an integer target.

Return the number of non-empty subsequences of nums such that the sum of the minimum and maximum element on it is less or equal than target.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: nums = [3,5,6,7], target = 9
Output: 4
Explanation: There are 4 subsequences that satisfy the condition.
[3] -> Min value + max value <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)

Example 2:

Input: nums = [3,3,6,8], target = 10
Output: 6
Explanation: There are 6 subsequences that satisfy the condition. (nums can have repeated numbers).
[3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]

Example 3:

Input: nums = [2,3,3,4,6,7], target = 12
Output: 61
Explanation: There are 63 non-empty subsequences, two of them don't satisfy the condition ([6,7], [7]).
Number of valid subsequences (63 - 2 = 61).

Example 4:

Input: nums = [5,2,4,1,7,6,8], target = 16
Output: 127
Explanation: All non-empty subset satisfy the condition (2^7 - 1) = 127

Constraints:

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

Solution: Two Pointers

Since order of the elements in the subsequence doesn’t matter, we can sort the input array.
Very similar to two sum, we use two pointers (i, j) to maintain a window, s.t. nums[i] +nums[j] <= target.
Then fix nums[i], any subset of (nums[i+1~j]) gives us a valid subsequence, thus we have 2^(j-(i+1)+1) = 2^(j-i) valid subsequence for window (i, j).

Time complexity: O(nlogn) // Sort
Space complexity: O(n) // need to precompute 2^n % kMod.

C++

// Author: Huahua

class Solution {

public:

int numSubseq(vector<int>& nums, int target) {

constexpr int kMod = 1e9 + 7;

const int n = nums.size();

vector<int> p(n + 1, 1);

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

p[i] = (p[i - 1] << 1) % kMod;

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

int ans = 0;

for (int i = 0, j = n - 1; i <= j; ++i) {

while (i <= j && nums[i] + nums[j] > target) --j;

if (i > j) continue;

// In subarray nums[i~j]:

// min = nums[i], max = nums[j]

// nums[i] + nums[j] <= target

// {nums[i], (j - i - 1 + 1 values)}

// Any subset of the right part gives a valid subsequence

// in the original array. And There are 2^(j - i) ones.

ans = (ans + p[j - i]) % kMod;

}

return ans;

}

};

花花酱 LeetCode 1013. Pairs of Songs With Total Durations Divisible by 60

By zxi on March 16, 2019

In a list of songs, the i-th song has a duration of time[i] seconds.

Return the number of pairs of songs for which their total duration in seconds is divisible by 60. Formally, we want the number of indices i < j with (time[i] + time[j]) % 60 == 0.

Example 1:

Input: [30,20,150,100,40]
Output: 3
Explanation: Three pairs have a total duration divisible by 60:
(time[0] = 30, time[2] = 150): total duration 180
(time[1] = 20, time[3] = 100): total duration 120
(time[1] = 20, time[4] = 40): total duration 60

Example 2:

Input: [60,60,60]
Output: 3
Explanation: All three pairs have a total duration of 120, which is divisible by 60.

Note:

1 <= time.length <= 60000
1 <= time[i] <= 500

Solution: Two Sum of 60

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

C++

// Author: Huahua, running time: 36 ms, 11.6 MB

class Solution {

public:

int numPairsDivisibleBy60(vector<int>& time) {

vector<int> c(60);

int ans = 0;

for (int t : time) {

t %= 60;

ans += c[(60 - t) % 60];

++c[t];

}

return ans;

}

};