4 weeks ago

Hrishabh Patel • 10

Dhanbad

#include <bits/stdc++.h>
using namespace std;

vector<int> encryptionValidity(int instructionCount, int validityPeriod, int keys[], int n){
   vector<int> ans(2, 0);
   long long tests = (long long)instructionCount * validityPeriod;
   ans[0] = (tests >= n);
   vector<int> strength(n, 1);
   sort(keys, keys + n); // sorting the array
   map<int, int> mpp;
   for(int i = 0; i < n; i++){
      mpp[keys[i]]++;
      for(int j = 1; j * j <= keys[i]; j++){
        if(keys[i]%j==0){
            if(mpp.find(j) != mpp.end()) strength[i]++;
            if(mpp.find(keys[i]/j) != mpp.end()) strength[i]++;
        }
      }
   }
   
   
   ans[1] = (int)1e5 * (*(max_element(strength.begin(), strength.end())));

   return ans;
}

int main(){
  // driver code
  // Example usage:
  int keys[] = {2, 4, 2, 8};
  int n = sizeof(keys) / sizeof(keys[0]);
  vector<int> result = encryptionValidity(1000, 10000, keys, n);
  cout << result[0] << " " << result[1] << endl;
  return 0;
}

Time Complexity  = nlogn + nsqrt(max(key[i]));