Leetcode discuss: 1015. Smallest Integer Divisible by K

July 8, 2022

Here is the link. 

C# | Quick learner | Work on %k - remainder instead

July 8, 2022
Introduction
I chose to study one of C# discuss post, and then I learned quickly to write a working solution.

Remainder | %k calculation
It is important to design the algorithm to avoid overflow. The number can be out of range of C# Int64.

Also there is concern to avoid deadloop in search. The way to detect deadloop is to save all remainders visited before.

The following C# code passes online judge.

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

namespace _1015_smallest_integer
{
    class Program
    {
        static void Main(string[] args)
        {
            // 20565018 - the answer 
            var result = SmallestRepunitDivByK(123456789);
        }

        /// <summary>
        /// study code
        /// https://leetcode.com/problems/smallest-integer-divisible-by-k/discuss/1656233/C-solution
        /// </summary>
        /// <param name="k"></param>
        /// <returns></returns>
        public static int SmallestRepunitDivByK(int k)
        {
            var remainder = 0;
            var length = 0;

            var set = new HashSet<int>();

            // 1. Understand the approach to work on remainder - n may not fit in a 64-bit signed integer
            // 2. Smallest one - Brute force solution - start from 1, 11, continuously apply * 10 on remainder
            // 3. remainder is always an integer - int32 
            // 4. If the remainder gets into a value visted before, then there is a deadloop - break the search
            // If you understand the above four points, then start to read the code. 
            while (true)
            {
                remainder = (remainder * 10 + 1) % k;
                length++;

                if (remainder == 0)
                {
                    return length;
                }
                else
                {
                    // 3. Avoid deadloop
                    if (set.Contains(remainder))
                    {
                        break;
                    }
                    else
                    {
                        set.Add(remainder);
                    }
                }
            }

            return -1;
        }
    }
}