• + 4 comments

    C# solution using BFS with optimization for when value <= 4. Pass all test cases.

    using System;
    using System.Collections.Generic;
    using System.IO;
    using System.Linq;
    class Solution {
        static void Main(String[] args) {
            int nQueries = Int32.Parse(Console.ReadLine());
    
            for(int i = 0; i < nQueries; i++)
            {
                int n = Int32.Parse(Console.ReadLine());
    
                var queue = new Queue<Node>();
                queue.Enqueue(new Node(n));
    
                while(queue.Any())
                {
                    Node current = queue.Dequeue();
    
                    if(current.Value <= 4)
                    {
                        if(current.Value == 4)
                            Console.WriteLine(current.Depth + 3);
                        else
                            Console.WriteLine(current.Depth + current.Value);
    
                        break;
                    }
                    
                    queue.Enqueue(new Node(current.Value - 1, current.Depth + 1));
    
                    int start = (int)Math.Sqrt(current.Value);
                    for(int j = start; j >= 2; j--)
                    {
                        if(current.Value % j == 0)
                            queue.Enqueue(new Node(current.Value / j, current.Depth + 1));
                    }
                }
            }
        }
    }
    
    struct Node
    {
        public int Value;
        public int Depth;
    
        public Node(int value)
        {
            Value = value;
            Depth = 0;
        }
    
        public Node(int value, int depth)
        {
            Value = value;
            Depth = depth;
        }
    }