In this guide, you will get 923. 3Sum With Multiplicity LeetCode Solution with the best time and space complexity. The solution to Sum With Multiplicity problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Given an integer array arr, and an integer target, return the number of tuples i, j, k such that i < j < k and arr[i] + arr[j] + arr[k] == target.
As the answer can be very large, return it modulo 109 + 7.
Input: arr = [1,1,2,2,2,2], target = 5
Output: 12
Explanation:
arr[i] = 1, arr[j] = arr[k] = 2 occurs 12 times:
We choose one 1 from [1,1] in 2 ways,
and two 2s from [2,2,2,2] in 6 ways.
Example 3:
Input: arr = [2,1,3], target = 6
Output: 1
Explanation: (1, 2, 3) occured one time in the array so we return 1.
923. 3Sum With Multiplicity LeetCode Solution in C++
class Solution {
public:
int threeSumMulti(vector<int>& arr, int target) {
constexpr int kMod = 1'000'000'007;
int ans = 0;
unordered_map<int, int> count;
for (const int a : arr)
++count[a];
for (const auto& [i, x] : count)
for (const auto& [j, y] : count) {
const int k = target - i - j;
const auto it = count.find(k);
if (it == count.cend())
continue;
if (i == j && j == k)
ans = (ans + static_cast<long>(x) * (x - 1) * (x - 2) / 6) % kMod;
else if (i == j && j != k)
ans = (ans + static_cast<long>(x) * (x - 1) / 2 * it->second) % kMod;
else if (i < j && j < k)
ans = (ans + static_cast<long>(x) * y * it->second) % kMod;
}
return ans;
}
}; /* code provided by PROGIEZ */
923. 3Sum With Multiplicity LeetCode Solution in Java
class Solution {
public int threeSumMulti(int[] arr, int target) {
final int kMod = 1_000_000_007;
int ans = 0;
Map<Integer, Integer> count = new HashMap<>();
for (final int a : arr)
count.merge(a, 1, Integer::sum);
for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
final int i = entry.getKey();
final int x = entry.getValue();
for (Map.Entry<Integer, Integer> entry2 : count.entrySet()) {
final int j = entry2.getKey();
final int y = entry2.getValue();
final int k = target - i - j;
if (!count.containsKey(k))
continue;
if (i == j && j == k)
ans = (int) ((ans + (long) x * (x - 1) * (x - 2) / 6) % kMod);
else if (i == j && j != k)
ans = (int) ((ans + (long) x * (x - 1) / 2 * count.get(k)) % kMod);
else if (i < j && j < k)
ans = (int) ((ans + (long) x * y * count.get(k)) % kMod);
}
}
return ans;
}
} // code provided by PROGIEZ
923. 3Sum With Multiplicity LeetCode Solution in Python
class Solution:
def threeSumMulti(self, arr: list[int], target: int) -> int:
kMod = 1_000_000_007
ans = 0
count = collections.Counter(arr)
for i, x in count.items():
for j, y in count.items():
k = target - i - j
if k not in count:
continue
if i == j and j == k:
ans = (ans + x * (x - 1) * (x - 2) // 6) % kMod
elif i == j and j != k:
ans = (ans + x * (x - 1) // 2 * count[k]) % kMod
elif i < j and j < k:
ans = (ans + x * y * count[k]) % kMod
return ans % kMod # code by PROGIEZ
