can anyone explain the logic to solve the problem with a clear bit explanation…as iam unable to get answer for this problem from different platforms…hope you guys help me …
and link is as follows
This problem can be solved easily by using recursion. To put it simply you just have to try all possibilities from all the given numbers in the array and try to construct a new array in which for each i in [0, n-1), a[i+1] = (a[i]/3 or a[i] * 2). Therefore, we just use recursion by considering all a[i] as starting points of our answer.
Consider the following example:
input:
4
42 28 84 126
Explanation:
Let res as the final result array.
First I consider 42 as the first number and add it to res. Now 42%3 == 0 but 42/3 is not present in array a. So now we have to check for 42 * 2 = 84 which is present in a. so we add 84 in res. Similarly we check for (84/3 and 84%3 == 0) and 84 * 2. Now at some point in the recursion for the current x if both x/3 and x * 2 are not possible to add to res then we discard the recently added number from res. This way we construct the array res until its size becomes n by choosing all possibilities. Here is the link to my solution:
P.S. my solution is pretty big as compared to the solution given in their editorial but trust me this is easier to implement because of the constraints.
nice explaination bro…can i get your email id…as iam unable to get the approaches for some problems then i will ask you bro…if you dont mine can you give your email id plz…
I solved it using DFS
If you can get from one number to another then imagine there’s an edge between them.
Now do DFS and store the leaf nodes. Now if the series from one leaf node to another is valid then we have the answer, else reverse that series (since it’s given that answer will always exist)
See the code, you’ll get it.
#include <bits/stdc++.h>
using namespace std;
#define int long long
map<int,set<int>> adj;
vector<int> leaf;
map<int,bool> visit;
vector<int> res;
void dfs1(int src){
visit[src]=true;
bool isLeaf=true;
for(int x:adj[src]){
if(!visit[x]){
isLeaf = false;
dfs1(x);
}
}
if(isLeaf) leaf.push_back(src);
return;
}
void dfs2(int src){
visit[src]=true;
res.push_back(src);
for(int x:adj[src]){
if(!visit[x]){
dfs2(x);
}
}
}
bool isValid(vector<int> &a){
for(int i = 1 ; i < a.size() ; i++)
if(a[i] != 2*a[i-1] && (a[i-1]%3 == 0 ? a[i] != a[i-1]/3:true)) return false;
return true;
}
int32_t main(){
int n;
cin >> n;
vector<int> a(n);
for(int i = 0; i < n ; i++) cin >> a[i];
for(int i = 0; i < n ; i++){
int x = a[i];
int y = 2*a[i];
if( find(a.begin(), a.end(),y) != a.end() ){
adj[x].insert(y);
adj[y].insert(x);
}
if(a[i]%3==0){
y = a[i]/3;
if( find(a.begin(), a.end(),y) != a.end() ){
adj[x].insert(y);
adj[y].insert(x);
}
}
}
dfs1(a[0]);
visit.clear();
dfs2(leaf[0]);
if( isValid(res) ){
for(int i = 0; i < n ; i++) cout << res[i] << ' ';
cout << endl;
}else{
reverse(res.begin(), res.end());
for(int i = 0; i < n ; i++) cout << res[i] << ' ';
cout << endl;
}
return 0;
}
I just looked at it, but cant you find the power of 2 and 3 in each number and just sort that by making a a tuple<power if 2,- power of 3, number it self>, sort and print the third number, but it says n<100 so i don’t know why it won’t work
#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <vector>
#define ll long long int
#define mp make_pair
#define pb push_back
#define vi vector<int>
using namespace std;
int main(){
int n;
cin>>n;
tuple <int,int,ll> seq[n];
for(int i=0;i<n;i++){
long long int a;
cin>>a;
get<2>(seq[i])=a;
get<0>(seq[i])=0;
get<1>(seq[i])=0;
while(a%2==0){
a/=2;
get<0>(seq[i])++;
}
while(a%3==0){
a/=3;
get<1>(seq[i])--;
}
}
sort(seq,seq+n);
for(int i=0;i<n;i++){
cout<<get<2>(seq[i])<<" ";
}
}
Ok that does work.