priyam2k

Untitled

Sep 22nd, 2019
154
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.81 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int main() {
  6.     vector<pair<int,int>> v;
  7.     int n,k,i;
  8.     cin>>n>>k;
  9.     int a[n];
  10.     for(i=0;i<n;i++){
  11.         cin>>a[i];
  12.         if(a[i]%k!=0){
  13.             v.push_back(make_pair(a[i],i));
  14.             v.push_back(make_pair(a[i]*k,i));
  15.         }
  16.         else{
  17.             while(a[i]%k==0){
  18.                 v.push_back(make_pair(a[i],i));
  19.                 a[i]=a[i]/k;
  20.             }
  21.         }
  22.        
  23.     }
  24.     int l=0,cnt=0,f[n+1];//freq array
  25.     for(i=0;i<v.size();i++){
  26.         f[v[i].second]++;
  27.         if(f[v[i].second]==1)
  28.             cnt++;
  29.         while(l<=i && f[v[i].second]>1){
  30.             f[v[i].second]--;
  31.             l++;
  32.         }
  33.         if(cnt==n){
  34.             ans=min(ans,f[v[i].first]-f[v[l].first);
  35.         }
  36.     }
  37. cout<<ans;
  38. }
Add Comment
Please, Sign In to add comment