You are viewing a single comment's thread. Return to all 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; } }
Down to Zero II
You are viewing a single comment's thread. Return to all comments →
C# solution using BFS with optimization for when value <= 4. Pass all test cases.