Please provide hint for this problem ( see description )

general
1

https://mycode.prepbytes.com/problems/arrays/EVENMAT

2

It is always possible to make any two odd elements even without changing the rest of the array’s parity. So, if the number of odd elements is even, the answer is YES, otherwise NO.

1 Like
3

Thanks a lot for helping me :smile:
can you please give hint for this problem too:-

4
5

My approach to solve the above problem:-

It is given that Ai + Aj= Ai/Aj . From this equation we can derive that
Ai = (Aj*Aj) / (1-Aj )

From the above equation we can say that for every Aj we can have Ai that is equal to (Aj*Aj) / (1-Aj ) and if (i<j) than we can get a valid pair.

6

This is my code for the same problem but its giving wrong answer

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll; 

int main()
{
  //write your code here    
  
  int t ; cin>>t ;
  for(int i=0;i<t;i++)
  {
      int n; cin>>n; int arr[n];
      
      for(int j=0;j<n;j++) cin>>arr[j]; 
      
      unordered_map<int,int>map; 
      ll ans=0;
      
      for(int k=0;k<n;k++)
      {
          if(k==0)
          {
              map[arr[k]]++; 
          }
          else
          {
              if(arr[k]!=1)
              {
                  double val=(double)(arr[k]*arr[k])/(double)(1-arr[k]); 
                  double f=floor(val); 
                  if(val-f==0)
                  {
                      int x=val; 
                      if(map.find(x)!=map.end())
                      {
                          ans+=map[x];
                      }
                      
                  }
              }
              map[arr[k]]++;
          }
          
          
      }
      
      cout<<ans<<endl;
  }


  return 0;
}
7

your logic is correct but your implementation has a lot of redundancies.
It fails for cases like,

TC 
1
4
0 0 0 0
CORRECT OUTPUT: 0
AC_CODE 
#include <bits/stdc++.h>
using namespace std;
void solve(){
  int n ; cin >> n ;
  vector<int>a(n) ;
  for(int &x:a)
    cin >>  x ;
  map<int,int>c ; 
  int ans =0 ;
  for(int i=0;i<n;i++){
    if(a[i]&&a[i]!=1&&(a[i]*a[i])%(1-a[i])==0)
      ans+=c[(a[i]*a[i])/(1-a[i])] ;
    c[a[i]]++ ;
  }
  cout <<  ans << '\n'  ;
}
int main(){
  int TC ;
  cin >> TC  ;
  while(TC--)
    solve() ;
}
1 Like
8

Thanks a lot I got AC :smile:

I have a doubt :-
if our array is [ -3, -3, -3, 2 ] than expected output must be 3
explanation : for the following pair of index we have Ai+Aj = Ai/Aj and i<j
(0,3) ,(1,3) , (2,3)

But our code is giving output as 0

Try this test case :-
Input
1
4
-3 -3 -3 2
Expected Output
3
Explanation :- for pair (0,3) we have Ai+Aj=-3+2=-1 and Ai/Aj = -3/2 =-1
so Ai+Aj=Ai/Aj also i<j.

9

-3/2 = -1.5 not -1

1 Like
10

Oo…yes thanks a lot :laughing: