Alright, let’s talk about this ‘number 1015’ thing I wrestled with recently. Wasn’t a project code or anything fancy, just one of those coding challenges someone threw my way. The task seemed simple enough on the surface: find the smallest number made up of only the digit ‘1’ that’s divisible by a given number K. And you just need the length of that number of ones.
So, my first thought, like probably anyone’s, was pretty straightforward. Let’s just build the number. Start with 1. Is it divisible by K? No. Okay, try 11. Divisible by K? No. Try 111. Keep going, right? Just tack on a ‘1’ each time and check the division.
Man, that fell apart fast.
Tried it with a K like 3. Okay, 1? No. 11? No. 111? Yes! Length is 3. Easy peasy.
Then I tried a bigger K. The number made of ones just got huge, like, really huge, incredibly quickly. Way too big for standard integer types in most languages. It just overflowed. Totally useless approach for anything but the smallest K values. Sat there staring at it for a bit, thinking this can’t be the way.
Figuring Out the Trick
Had to rethink it. The key thing I eventually realized is that you don’t actually need the gigantic number itself. What matters is the remainder when you divide by K. If a huge number `N` has a remainder `R` when divided by K, then the next number, `N10 + 1`, will have a remainder of `(R10 + 1) % K`.
So, the process became:
- Start with a remainder `rem = 1` (representing the number ‘1’) and length `len = 1`.
- Check if `rem` is 0. If yes, we found it, the answer is `len`.
- If not, calculate the next remainder: `rem = (rem 10 + 1) % K`.
- Increment the length: `len = len + 1`.
- Repeat the check and calculation.
This way, the numbers involved never get bigger than K. Much better. No more overflow headaches.
But there was a catch.
What if K is, say, 2? Or 5? Or 10? Any number divisible by 2 or 5? A number made of only ones will always end in ‘1’. It can never be divisible by 2 or 5. Spent a few minutes wondering why my loop wasn’t ending for K=2. Duh. If K is divisible by 2 or 5, no solution exists. You just return -1 or whatever indicates failure. Had to add that check right at the beginning.
Also, you need to watch out for repeating remainders. If you get a remainder you’ve seen before, you’re stuck in a loop and will never reach a remainder of 0. So, I added a quick check, keeping track of remainders I’d already encountered. If a remainder repeats, boom, also return -1.
Got it all coded up after that. Tested it with a bunch of different K values, including the tricky ones. It worked. It felt pretty good to sort that out, turning a brute-force mess into something neat using remainders. Simple math trick, really, but finding it under pressure is the fun part. Just one of those small battles you win during a day of coding.
