## 977D — Divide by three, multiply by two

We can see that all numbers in given sequence are distinct. since all numbers in sequence are of the form . Hence if

*a*_{i}=*a*_{j}then = = 2^{x - m}= 3^{y - n}which is not possible because any power of 2 will be an even number and any power of 3 will be an odd number.if there exists in sequence then 2 *

*a*_{i}can not be in sequence and vice versa. We can prove it using contradiction. Suppose there is a number*a*_{i}such that both and 2 **a*_{i}exists in sequence. by little bit of tricks this = , this again is not possible by same argument as above, we just have to change the order of exponents.Hence for each

*a*_{i}in sequence we see if or 2 **a*_{i}is present(remember that only one of them can be present). Now if there is any*a*_{i}such that both and 2 **a*_{i}is not in sequence then this should be*a*_{n}. if there is any such*a*_{i}that for all 0 ≤*j*≤*n*: ≠*a*_{i}AND 2 **a*_{i}≠*a*_{i}, then this is*a*_{1}.Once you have got

*a*_{1}, you keep on producing sequence just by doing binary search for and 2 **a*_{i}(remember only one of them is present so once you find it you print it).

Auto comment: topic has been updated by aMitkvikram (previous revision, new revision, compare).Can you explain your 1st statement ?

I have updated the first statement. Note that any power of 2 will be even and any power of 3 will be odd, hence (power of 2) can not be equal to (power of 3).

Auto comment: topic has been updated by aMitkvikram (previous revision, new revision, compare).https://codeforces.com/contest/977/submission/38108720 I wrote a simple comparator function to sort the array. Math is similar.

There are many ways to solve this problem but your solution is concise. I solved it using dfs.