If the given input $$$n$$$ is $$$1$$$, the answer will always be $$$2$$$. If the given input $$$n$$$ is divisible by $$$3$$$, that is the minimum distance to reach there. However, if it is not, it means the number is either $$$1$$$ or $$$2$$$ less than any number divisible by $$$3$$$. So, if it's less than by $$$2$$$, we can just add $$$1$$$ to our answer since we can take $$$2$$$ steps. If it's less than by $$$1$$$, we can also add $$$1$$$ to our answer because we will take $$$(n//3)−1$$$ steps and additional $$$3+1=4$$$ steps, which is two $$$2$$$ steps. This means the original answer will be $$$(n//3)$$$ and if the number is not divisible by$3$, we can just add $$$1$$$ to our answer.

for _ in range(int(input())):
    n = int(input())
    if n == 1:
        print(2)
        continue

    ans = n // 3 
    # if n is either less by 1 or 2 from any number divisible by 3
    # if it's less by 1 we can take (n // 3) - 1 step and additional 2 * 2 step 
    # if it's less by two we can take (n // 3) step and 2 additional step
    if n % 3:
        ans += 1

    print(ans)

The problem is about considering the least amount of cases possible. I propose the following options.

If $$$x≠1$$$, then you can always print n ones. So the answer is $$$YES$$$.

If $$$k=1$$$, then no integer is available, so the answer is $$$NO$$$.

If $$$k=2$$$, then only $$$2$$$ is available, so you can only collect even $$$n$$$. So if it's odd, the answer is $$$NO$$$.

Otherwise, you can always collect n with the following construction: if $$$n$$$ is even then take $$$2$$$, otherwise take $$$3$$$. Then take $$$\left\lfloor \frac{n}{2} \right\rfloor - 1$$$ twos. You can see that an even $$$n$$$ only uses twos, so it fits the previous check. If it's odd, then $$$k$$$ is at least $$$3$$$, so $$$3$$$ is allowed to take.

Overall complexity: $$$O(n)$$$ per testcase.

import sys
for _ in range(int(input())):
    n, k, x = map(int, sys.stdin.readline().strip().split())
    if x != 1:
	print("YES")
	print(n)
	print(*([1] * n))
    elif k == 1 or (k == 2 and n % 2):
	print("NO")

    else:
	print("YES")
	print(n // 2)
		
	print(*([2] * (n // 2 - 1)) + [3 if n % 2 == 1 else 2])
    

Let's sort the edges by their weight in descending order and merge the vertices in that order. Whenever you get an already merged vertices, it means the new edge will create cycle; we can update our answer to that edge. Finally, to get the cycle, we can do DFS from either end of that edge until we get to the other end.

from collections import defaultdict
from sys import stdin


def input(): return stdin.readline().strip()

class DSU:
    def __init__(self, n):
        self.p = [i for i in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, v):
        while v != self.p[v]:
            self.p[v] = self.p[self.p[v]]
            v = self.p[v]
        return v
    
    def merge(self, u, v):
        pu = self.find(u)
        pv = self.find(v)
        if pu == pv:
            return False
        if self.size[pu] < self.size[pv]:
            pu, pv = pv, pu
        self.size[pu] += self.size[pv]
        self.p[pv] = pu
        return True

T = int(input())
for _ in range(T):
    N, M = map(int, input().split())
    edges = []
    adj = defaultdict(list)
    for __ in range(M):
        u, v, w = map(int, input().split())
        u, v = u - 1, v - 1
        edges.append((w, u, v))
        adj[u].append(v)
        adj[v].append(u)

    edges.sort(key=lambda edge: edge[0], reverse=True)
    dsu = DSU(N)
    for w, u, v in edges:
        if not dsu.merge(u, v):
            ans = (w, u, v)

    min_w, st, end = ans
    stk = [st]


    # DFS to get the cycle
    p = [-1]*N
    p[st] = st
    while stk:
        v = stk.pop()
        for ch in adj[v]:
            if v == st and ch == end: continue
            if ch == end:
                p[ch] = v
                stk = []
                break
            if p[ch] == -1:
                p[ch] = v
                stk.append(ch)
    v = end
    path = []
    while p[v] != v:
        path.append(v)
        v = p[v]
    path.append(st)

    print(min_w, len(path))
    for i in range(len(path)):
        path[i] += 1
    print(*path)

Conclusion first:

First, we transform each digit of the original number as follows:

$$$0$$$, $$$1$$$ $$$\Rightarrow$$$ empty

$$$2$$$ $$$\Rightarrow$$$ $$$2$$$

$$$3$$$ $$$\Rightarrow$$$ $$$3$$$

$$$4$$$ $$$\Rightarrow$$$ $$$3,2,2$$$

$$$5$$$ $$$\Rightarrow$$$ $$$5$$$

$$$6$$$ $$$\Rightarrow$$$ $$$5,3$$$

$$$7$$$ $$$\Rightarrow$$$ $$$7$$$

$$$8$$$ $$$\Rightarrow$$$ $$$7,2,2,2$$$

$$$9$$$ $$$\Rightarrow$$$ $$$7,3,3,2$$$

Then, sort all digits in decreasing order as a new number, then it will be the answer.

Proof:

We can observe that our answer won't contain digits $$$4,6,8,9$$$, because we can always transform digits $$$4,6,8,9$$$ to more digits as in the conclusion, and it makes the number larger.

Then, how can we make sure that the result is the largest after this transformation?

We can prove the following lemma:

For any positive integer $$$x$$$, if it can be written as the form $$$(2!)^{c_2}\times (3!)^{c_3}\times (5!)^{c_5}\times (7!)^{c_7}$$$, there will be only one unique way.

Suppose that there exists two ways to write down x in this form, we can assume that the two ways are $$$(2!)^{a_2}\times (3!)^{a_3}\times (5!)^{a_5}\times (7!)^{a_7}$$$ and $$$(2!)^{b_2}\times (3!)^{b_3}\times (5!)^{b_5}\times (7!)^{b_7}$$$.

We find the largest $$$i$$$ such that $$$ai ≠ bi$$$, Then we know there exists at least one prime number whose factor is different in the two ways.

But according to the Fundamental Theorem of Arithmetic, there is only one prime factorization of each integer. So we get a contradiction.

After getting the result, we don't need to worry about other numbers being larger than ours.

Time Complexity: $$$O(n)$$$.

N = int(input())
num = input()

digits = []
for digit in num:
    if digit == '4':
        digits.extend(['3','2', '2'])
    elif digit == '6':
        digits.extend(['5', '3'])
    elif digit == '8':
        digits.extend(['7', '2', '2', '2'])
    elif digit == '9':
        digits.extend(['7', '3', '3', '2'])
    elif digit in "2357":
        digits.append(digit)

digits.sort(reverse=True)

print("".join(digits))

First of all, always comparing strings takes quite a long time, so let's create a graph using an $$$ n \times n $$$ grid where $$$graph_{i,j} = 1$$$ denotes that the $$$ith$$$ and $$$ jth$$$ song can be consecutive and $$$0$$$ otherwise. Now, we can do a dynamic programming solution over subsets.

We denote mask as our current bit-mask and we say it has the value of all elements we include. For example, if our mask is equal to 7, in binary it looks like ...000111, so we can say that we included elements 0, 1 and 2. Each power of two set in our mask, implies we include that element.

So now, if we iterate over masks and the last included element, we can mark dpmask,i

as a boolean which tells whether it is possible to get to this state. We transition from a state to another by using the current mask and trying to include all non-included elements one-by-one, and checking out if it is possible to include them. If it is, we update our new mask.

After calculating for each state whether we can get to it, using previously calculated states, we update our answer as the maximum number of included elements (bits set) in a mask which is obtainable.

import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")


for _ in range(int(input())):
   n = int(input())
   g = [[0] * n for _ in range(n)]
   a = [input().split() for _ in range(n)]


   for i in range(n):
       for j in range(i):
           if a[i][0] == a[j][0] or a[i][1] == a[j][1]:
               g[i][j] = g[j][i] = 1
  
   dp = [[0] * n for _ in range(1 << n)]


   for i in range(n):
       dp[1 << i][i] = 1


   ans = 1


   for i in range(1, 1 << n):
       for j in range(n):
           if dp[i][j]:
               takes = bin(i).count('1')
               ans = max(ans, takes)
               for k in range(n):
                   if i & (1 << k) == 0 and g[j][k] == 1:
                       dp[i | 1 << k][k] = 1
  
   print(n - ans)