fork download
copy 
  1. /*
  2. AMAZON OA
  3. Understanding :- Given two arrays “A” and “B” -> do minimum number of operations to make sure A[i]!=B[i]
  4.  
  5. -> In one operation you can swap (i,j) on array A 
  6. */
  7.  
  8. /*******************************/
  9.  
  10.  
  11.  
  12.  
  13. #include<iostream>
  14. #include<algorithm>
  15. #include<math.h>
  16. #include<vector>
  17. #include<queue>
  18. #include<unordered_map>
  19.  
  20. using namespace std;
  21.  
  22. int main()
  23. {
  24.     int opr = 0;
  25.     // vector<int> arr1= {1, 5, 3, 1, 3};
  26.     // vector<int> arr2= {1, 5, 3, 5, 1};
  27.     vector<int> arr1= {2, 2, 1, 1, 2};
  28.     vector<int> arr2= {2, 1, 1, 1, 2};
  29.     priority_queue<pair<int, int> >badbonds;
  30.     vector<pair<int , int> >goodbonds;
  31.     unordered_map<int, int>cnt;
  32.  
  33.     for(int i=0; i<arr1.size(); i++)
  34.     {
  35.         if(arr1[i]==arr2[i]) cnt[arr1[i]]++;
  36.         else goodbonds.push_back({arr1[i], arr2[i]});
  37.     }
  38.  
  39.     int maxFreq = 0;
  40.     for(auto it: cnt)
  41.     {
  42.         badbonds.push({it.second, it.first});
  43.         maxFreq = max(maxFreq, it.second);
  44.     }
  45.  
  46.     while(badbonds.size()>1) //run unitl a single badbond is left which cannot be paired with any badbond as it is the single one left
  47.     {
  48.         auto firstbond = badbonds.top();
  49.         badbonds.pop();
  50.         auto secondbond = badbonds.top();
  51.         badbonds.pop();
  52.         int freq_diff = firstbond.first - secondbond.first;
  53.         opr += secondbond.first;
  54.  
  55.         for(int i=1; i<=secondbond.first ; i++) //thi is number of swaps you are doing and  after this much number of operation all those became goodbond and it might be that we
  56.         //can use them for further swapping in future so save them in the goodbond array.
  57.         {
  58.             //if 33 and 55 and after swapping we will get two good bonds 35 and 53
  59.             goodbonds.push_back({firstbond.second, secondbond.second});
  60.             goodbonds.push_back({secondbond.second, firstbond.second});
  61.         }
  62.  
  63.         if( freq_diff > 0) badbonds.push({freq_diff, firstbond.second});
  64.         if(badbonds.empty()) //i.e if zero then we are done hereitself
  65.         {
  66.             cout << " Got ans: " << opr << endl;
  67.             return 0;
  68.         }
  69.     }
  70.  
  71.     auto badbondleft = badbonds.top();
  72.  
  73.     for(int i=0; i<goodbonds.size(); i++) //use the goodbonds to tackle the badbond left
  74.     {
  75.         if(badbondleft.second != goodbonds[i].first && badbondleft.second != goodbonds[i].second) //use goodbond only if badbone swapping element does not 
  76.         //becomes equal to any one of the two goodly bonded element
  77.         {
  78.              badbondleft.first--;
  79.              opr++;
  80.         }
  81.         if(!badbondleft.first)
  82.         {
  83.             cout << "Got ans: " << opr << endl;
  84.             return 0;
  85.         }
  86.     }
  87.  
  88.     cout << "not possible to solve return -1" << endl;
  89.  
  90.  
  91.     return 0;
  92. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
 Got ans: 2
https://ideone.com/mXdfDX
language:
C++ (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!