Leetcode 1201 - weekly contest 155 - algorithm I wrote in the contest - I noticed the timeout issue, but I could not figure out the optimal solution.

1202_weeklyContest155.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace nthUglyNumber
{
    class Program
    {
        static void Main(string[] args)
        {
            //var result = NthUglyNumber(3, 2, 3, 5); 
            var result = NthUglyNumber(1000000000, 2, 217983653, 336916467); 
        }

        /// <summary>
        /// brute force solution to search nth number
        /// </summary>
        /// <param name="n"></param>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <param name="c"></param>
        /// <returns></returns>
        public static int NthUglyNumber(int n, int a, int b, int c)
        {
            var numbers = new int[] { a, b, c };
            Array.Sort(numbers);

            int index = 0;
            var counts = new int[3];
            var previous = numbers[0];
            var current = previous;

            while(index < n)
            {
                if (index == 0)
                {
                    current = previous;
                    counts[0]++;
                }
                else
                {
                    var first  = (counts[0] + 1) * numbers[0];
                    var second = (counts[1] + 1) * numbers[1];
                    var third  = (counts[2] + 1) * numbers[2];

                    var next = new int[] { first, second, third };
                    var min = next.Min();
                    if (first == min)
                    {                        
                        var extraStep = (second - first) / numbers[0];
                        index += extraStep;
                        counts[0] = 1 + extraStep;
                        current = min + extraStep * numbers[0];                        
                    }
                    else if (second == min)
                    {
                        counts[1]++;
                        current = second; 
                    }
                    else if(third == min)
                    {
                        counts[2]++;
                        current = third; 
                    }
                    
                    previous = current; 
                }

                index++;
            }

            return current; 
        }
    }
}