what's wrong with my code [ Dfs , Dynamic programming ]

Question

i tried to solve this problem with dfs and dynamic programming . then i submit my code to my school grader but the answer is wrong . am i implement something wrong with dfs . what's wrong with my code.

PS.sorry for my bad english

The problem :

given a random number there's 2 different way you can do with this number
1.divide it by 3 (it has to be divisible)
2.multiply it by 2

given n number find the original order before it was swapped
----EXAMPLE1----
INPUT : 6
4 8 6 3 12 9
OUTPUT : 9 3 6 12 4 8
----EXAMPLE2----
INPUT : 4
42 28 84 126
OUTPUT : 126 42 84 28

Here's my code

#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
int n ;
int input[51];
map<int,int> order ;
map<int,int> memo ;

bool valid(int a){
    for(int i=0;i<n;i++){
        if(input[i]==a)return 1 ;
    }
    return 0 ;
}
void dfs(int st){
    memo[st]=1;
    if(valid(st/3)){
        if(memo[st/3]==0){
            dfs(st/3);
            order[st]+=order[st/3];
        }
        else order[st]+=order[st/3];
    }
    if(valid(st*2)){
        if(memo[st*2]==0){
            dfs(st*2);
            order[st]+=order[st*2];
        }
        else order[st]+=order[st*2];
    }
}

int main(){
    cin >>  n ;
    for(int i=0;i<n;i++){
        cin >> input[i];
        memo[input[i]]=0;
        order[input[i]]=1;
    }
    for(int i=0;i<n;i++){
        if(memo[input[i]]==0)dfs(input[i]);
    }

    for(int i=n;i>=1;i--){
        for(int k=0;k<n;k++){
            if(order[input[k]]==i){
                printf("%d ",input[k]);
                break;
            }
        }
    }
}

---

• Information the OP should have told us in the first place:

my code gave the correct answer only 7 of 10 test case .i've already asked my teacher he only told me to be careful with the recursion . but i couldn't figure it out what's wrong with my recursion or something else

• An example that "fails":

Here's a failing case: Say you have the sequence 3 1 2 4. valid will return true for 4 / 3 because it sees 1 in the sequence. – Calculuswhiz

• the better solution

#include<bits/stdc++.h>
using namespace std;
struct number{
    long long int r , f3 , f2 ;
};
vector<number> ans ;
bool cmp(number a,number b){
    if(a.f3!=b.f3)return a.f3>=b.f3;
    if(a.f2!=b.f2)return a.f2<=b.f2;
    return true ;
}
int main(){
    int n ;cin>> n ;
    long long int input ;
    
    for(int i=0;i<n;i++){
        cin >> input ;
        long long int r = input ;
        long long int f3 = 0, f2 = 0 ;
        while(input%3==0){
            f3++;
            input/=3;
        }
        while(input%2==0){
            f2++;
            input/=2;
        }
        ans.push_back({r,f3,f2});
    }
    sort(ans.begin(),ans.end(),cmp);

    for(auto i : ans){
        cout << i.r << " " ;
    }
}

Answer 1

The darkest place is under the lamp.

Look at the problem definition:

1.divide it by 3 (it has to be divisible)

Where do you test for the divisibility?

So, one error is here:

if(valid(st/3)){

This test should read:

if(st % 3 == 0 && valid(st/3)){

With this simple improvement, all three test cases pass.

A hint to improve (simplify) the solution

Numbers that are not divisible by 3 must come after those divisible. Similarly, those not divisible by 9 must be coming after those that does. Similarly for 27, 81,...

Now, if you divide your numbers into subsets of numbers of the form n = 3^k*m, where m % 3 != 0, then in each such a subset the only operation allowed by your algorithm is "multiply by 2". So it suffices to order them in ascending order.

The problem can be solved without dfs, nor is recurnece really necessary. Just order the numbers in a funny way: in descending order with respect to the number of times the number is divisible by 3, and then in ascending order. So, a task for you: challenge your teacher with a solution that, once the numbers are read in, does just one instruction std::sort (or qsort, as I see you write in C), then tests the validity of the solution, and prints it.

Moreover, I've just proved that if a solution exists, it is unique.