DIFFICULTY:
CAKEWALK PREREQUISITES:
None PROBLEM:
You’re given a sequence A_1, \dots, A_n. Find the number of pairs (i,j) such that A_i + A_j = A_i \cdot A_j. QUICK EXPLANATION:
Keep an eye on twos and zeros. EXPLANATION:
We may rewrite it as A_i=A_j(A_i-1), or A_j = \frac{A_i}{A_i-1}. Since A_j is integer it’s only possible when either A_i=A_j=2 or A_i=A_j=0, so we just have to calculate amount of occurences of 0's and 2's in the sequence.
The positives are 1+2+3+...n and negatives are -1-1-1... n times. So you can say its the sum of all positives from 1 to n and n*-1 or -n. There is a formula for sum of integers from 1 to n that is n*(n+1)/2 So now if you subtract n from it. It will become n*(n-1)/2 and you have to do it for both 0 and 2 and then add both
consider the case where c0=0 means no zero present then in denominator fact(c0-2) becomes fact(-2) . same error will occur for c0 =1 .Have you handled these cases ?
Just guess the error . If it is not the reason then post you code or submission link.
here in this question value of N≤40,000. Now assume that all are zero.In that senario is int capable of storing 400000! ? No lt can’t.Even long long is not capable of storing that huge value. So use the formula nC2 = n*(n-1)/2. In line no 19 change data type of ans[t] from int to long long and update the line no 42 to 50 as follows
long long pair=0;
if(c0>1)
{
pair+=(long long) (c0*(c0-1))/2;
}
if(c1>1)
{
pair+=(long long) (c1*(c1-1))/2;
}
N.B-You can also change the data type of c0,c1 as long long in that case you don’t need the type casting.
what is wrong in this code. I am getting WA. #include
#include<string.h>
using namespace std;
int main(){
int t,n;
cin>>t;
for(int i=0; i<n; i++){
cin>>n;
int arr[n];
int two=0, zero=0,coun=0,j;
for(j=0; j<n; j++){
cin>>arr[j];
if(arr[j]==2){
two++;
//cout<<two<<endl;
}
if(arr[j]==0){
zero++;
//cout<<zero<<endl;
}
}
//cout<<two<<" “<<zero;
coun=two*(two-1)/2 + zero*(zero-1)/2;
cout<<coun<<”\n";
}
}
There are only 2 cases to consider and we can consider them separately. If there is 0 and 0 and if there is 2 and 2. We can have a counter for the number of 0’s and the number of 2’s. Then we add up all the numbers below the # of 0’s and the # of 2’s. Code is below:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
int n;
int count(int a) {
ll sum = 0;
for(int i = 0; i <= a; i++) {
sum += i;
}
return sum;
}
void solve() {
cin >> n;
int a[n];
for(int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a, a + n);
int cnt = 0;
int counter = 0;
for(int i = 0; i < n; i++) {
if(a[i] == 2) {
cnt++;
}
if(a[i] == 0) {
counter++;
}
}
cout << count(cnt - 1) + count(counter - 1) << "\n";
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t--) {
solve();
}
}
