See the original problem on HackerRank.
Solutions
For each element in \(A\), we have to find the same element in \(B\). This is basically like performing the intersection between \(A\) and \(B\).
Then, since we have to change one element in \(B\) in any case:
- if the intersection is just \(A\), we return
A.size() - 1
- otherwise, we return
inters.size() + 1
Here is the idea in C++:
1
2
3
4
5
6
7
8
9
10
|
int beautifulPairs(vector<int>& A, vector<int>& B)
{
sort(begin(A), end(A));
sort(begin(B), end(B));
vector<int> inters;
set_intersection(begin(A), end(A), begin(B), end(B), back_inserter(inters));
if (inters.size() == A.size())
return inters.size() - 1;
return inters.size() + 1;
}
|
This solution costs \(O(N \cdot logN)\) because of using sort.
Since the domain is small we can either use a better sorting strategy (e.g. radix, counting sort) or we can just use a frequency table:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
int beautifulPairs(const vector<int>& A, const vector<int>& B)
{
array<int, 1000+1> freq{};
for (auto i : B)
freq[i]++;
auto cnt = 0;
for (auto i : A)
{
if (freq[i])
{
freq[i]--;
cnt++;
}
}
return cnt + (cnt == A.size() ? -1 : 1);
}
|
This solution is linear time and constant space. Consider the tradeoff: if the domain changes we might be forced to change the solution.
In Python we can simply use Counter:
1
2
3
4
5
6
7
8
9
10
11
|
def beautifulPairs(A, B):
ac = Counter(A)
bc = Counter(B)
pairs = 0
for val in ac:
if val in bc:
pairs += min(ac[val],bc[val])
if pairs == len(A):
return pairs - 1
else:
return pairs + 1
|
Rust solution with sort. Here we understand (because the language is explicit
about it) that we need to modify the original arrays (or make a copy of them).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
fn beautiful_pairs(mut a: Vec<usize>, mut b: Vec<usize>) -> usize {
let mut beautiful_count: usize = 0;
a.sort();
b.sort();
let mut a_iter = a.iter();
let mut b_iter = b.iter();
let mut ox = a_iter.next();
let mut oy = b_iter.next();
while let (Some(x), Some(y)) = (ox, oy) {
if x == y {
ox = a_iter.next();
oy = b_iter.next();
beautiful_count += 1;
} else if x > y {
oy = b_iter.next();
} else if x < y {
ox = a_iter.next();
}
}
if beautiful_count == a.len() {
beautiful_count - 1
} else {
beautiful_count + 1
}
}
|
But we don’t need to sort the array if we use the frequency table, so we can
pass an immutable slice instead of an owned Vec.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
pub fn beautiful_pairs(a: &[usize], b: &[usize]) -> usize {
let mut beautiful_count = 0;
let mut freq_table = [0; 1001];
for xb in b {
freq_table[*xb] += 1;
}
for xa in a {
if freq_table[*xa] > 0 {
freq_table[*xa] -= 1;
beautiful_count += 1;
}
}
if beautiful_count == a.len() {
beautiful_count - 1
} else {
beautiful_count + 1
}
}
|
The unsafe keyword here is needed to optimize the algorithm so the access to
an element of the frequency table is unchecked. We can safely do this until
all items in a and b have a value < 1001.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
fn beautiful_pairs(a: &[usize], b: &[usize]) -> usize {
let mut beautiful_count = 0;
let mut freq_table = [0; 1001];
unsafe {
for xb in b {
*freq_table.get_unchecked_mut(*xb) += 1;
}
for xa in a {
if *freq_table.get_unchecked(*xa) > 0 {
*freq_table.get_unchecked_mut(*xa) -= 1;
beautiful_count += 1;
}
}
}
if beautiful_count == a.len() {
beautiful_count - 1
} else {
beautiful_count + 1
}
}
|
The resulting asm can be compared
here