274A. k - Codeforces Solution C++

➤  Problem Link : 274A. k 

✅ C++ Solution :

 
#include<bits/stdc++.h>
using namespace std;
 
#define ll long long int
 
int main()
{
  ll n,k;
  cin>>n>>k;
  ll arr[n];
  unordered_map<ll,ll> parent;
  unordered_set<ll> st;
  for(ll i=0;i<n;i++)
  {
    cin>>arr[i];
  }
  sort(arr,arr+n);
  for(ll i=0;i<n;i++)
  {
     st.insert(arr[i]);
  }
  map<ll,vector<ll> > mp;
  for(ll i=0;i<n;i++)
  {
    if(k!=1 &&  arr[i]%k==0 && st.find(arr[i]/k)!=st.end())
    {
      parent[arr[i]]=parent[arr[i]/k];
      mp[parent[arr[i]]].push_back(arr[i]);
    }
    else
    {
      vector<ll> v(0);
      mp[arr[i]]=v;
      parent[arr[i]]=arr[i];
 
    }
  }
  ll ans=0,size;
  for(auto it=mp.begin();it!=mp.end();it++)
  {
    size=(*it).second.size() +1; // for itself
    ans+=size/2;
    if(size%2!=0)
      ans++;
  }
  cout<<ans;
 
}

 

Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook. 

😇Happy Learning!!

• Tweet
• Share
• Share
• Share
• Share

About Utkarsh Gupta

I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.