PROBLEM LINK:
PRACTICE
Editorialist:Indrajit Kabiraj
DIFFICULTY:
EASY
PREREQUISITES:
Number Theory ,Modulus
PROBLEM:
Santa is aware of the fact that children like candies so he ordered N boxes of candies. But when he received it he saw the number of candies in few boxes is not equal to the amount of candies on each box. So, now he wants to get the number of candies in each box equal. He can perform any of the two operations any number of times:
- He can divide A*i by 2,i.e the number of candies in Box i.
- He can divide A* i by 3,i.e the number of candies in Box i.
So Santa wants to make sure that after performing these two operations any number of times the amount of candies should be same in each and every box.
EXPLANATION:
If the candies are not equal in each boxes then we need to apply the operations as many times as possible.
Until we get a Constant which is not divisible by 2 or 3. After performing this operations on each boxes i.e A_i if we get an array with equal values on each boxes then we can make all the candies on each boxes equal otherwise not possible.
SOLUTION:
#include<bits/stdc++.h>
using namespace std;
int req(int x){
while(x%2==0 || x%3==0){
if(x%2==0){
x/=2;
}
else if(x%3==0){
x/=3;
}
}
return x;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin>>n;
set<int> s;
for(int i=0;i<n;i++){
int x;
cin>>x;
s.insert(req(x));
}
if(s.size()==1){
cout<<"Yes"<<endl;
}
else{
cout<<"No"<<endl;
}
}