You are given an array A containing N positive integers. Find the number of pairs (i,j) such that 1 \leq i \lt j \leq N and: A_i + A_j \geq A_i \cdot A_j
EXPLANATION:
A_i + A_j \geq A_i \cdot A_j is equivalent to (A_i - 1)(A_j - 1) \le 1, which can only happen when:
A_i = 1 or A_j = 1.
A_i = 2 and A_j = 2.
We can use some inclusion-exclusion to calculate the first case quickly: that is just the number of pairs with exactly one occurence of 1 - number of pairs with exactly two occurences of 1.
TIME COMPLEXITY:
Time complexity is O(N) for each test case.
SOLUTION:
Setter's Solution
for _ in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
one=a.count(1)
two=a.count(2)
ans = one*(n-one)
ans += (one*(one-1))//2
ans +=(two*(two-1))//2
print(ans)
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
ll n;
ll a[2001];
ll dp[2001];
void solve(){
cin >> n;
ll c1=0,c2=0;
for(int i=1; i<=n ;i++){
ll x;cin >> x;
if(x==1) c1++;
else if(x==2) c2++;
}
ll ans=c1*(n-c1)+c1*(c1-1)/2+c2*(c2-1)/2;
cout << ans << '\n';
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);
int t;cin >> t;while(t--) solve();
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t;
while (t--) {
int n; cin >> n;
int ones = 0, twos = 0;
for (int i = 0; i < n; i++) {
int u; cin >> u;
ones += (u == 1);
twos += (u == 2);
}
cout << 1LL * ones * (n - ones) + 1LL * ones * (ones - 1) / 2 + 1LL * twos * (twos - 1) / 2 << '\n';
}
}
It’s not really clear what you’re trying to do. Your logic is wrong and your code doesn’t pass the first example case.
There are three ways to reach a solution for each pair x, y:
x == 1 and y == 1. The number of solutions of this type is tri(ones - 1), where tri() is the triangular numbers function and ones is the number of ones in the set.
x == 2 and y == 2. Just like case 1, the number of solutions of this type is tri(twos - 1), where twos is the number of twos in this set.
x == 1 and y == anything. The number of solutions of this type is ones * not_ones, where not_ones is the number of numbers that aren’t one (ie n - one). (Rationale: each one can pair off with each not_one).
It’s well worth putting a tri() function into your template, because they crop up a lot in these problems.
I find the question ambiguous, If I am mistaken in understanding the question please do correct me, But as I understand it the problem is asking the number of pairs of ( i , j ) not number of unique pairs of (Ai, Aj) so if a case were as such
[1, 2, 3, 2, 4, 1, 2, 1, 1] then (1,2 ), (1,3), (1,4)…(1,9) should all be valid pairs among others like (2,4), (2,7), (6,7),(6,8),(6,9) and (8,9)
and I can’t imagine why one would need inclusion exclusion principle while trying to count pairs of indices, please clarify.
Your approach is absolutely correct.
The only mistake you are making is in line where you are updating ans for one.
Written by you
ans += (one/2)(2(n-1) + (1-one));
Correct line
ans += ((one)(2(n-1) + (1-one)))/2;
Explanation:
Instead of dividing one by 2, you must divide the whole term by 2 after performing multiplication. It is because if no. of one’s is odd then one/2 will not give required output.
yes thanks , after using long long int in every variable , code is accepted but i want to know why this code fails because in integer multiplication answer is stored in long long int variable so why we use every variable as long long int ???
Hey @parth1107
Thanks for asking your doubt.
Your logic is correct.
You have to just store the count of pairs in long int data type as the number of pairs can overflow in int data type.