How easy type conversion in Python helped me! A solution to problem from Code Jam 2019.

Foregone Solution — A problem from Google Code Jam's Qualifier Round this year felt like so easy to code.

You can checkout the full problem description at this LINK.

Problem(Source : Google Code Jam 2019 Website)

Someone just won the Code Jam lottery, and we owe them N jamcoins! However, when we tried to print out an over sized check, we encountered a problem. The value of N, which is an integer, includes at least one digit that is a 4... and the 4 key on the keyboard of our over sized check printer is broken.

Fortunately, we have a workaround: we will send our winner two checks for positive integer amounts A and B, such that neither A nor B contains any digit that is a 4, and A + B = N. Please help us find any pair of values A and B that satisfy these conditions.

Approach

While reading out the problem description, I read the input constraints and range which were around 10¹⁰⁰. So it was a bad idea to think of a very straight loop-based solution, that would strike the time complexity showing the nightmarish message “ Time limit Exceeded ! ”.

So I thought of dealing this with the help of strings. Python saved me!

Assuming you’ve read the problem description through the link above, there is a number N which may contain the digit 4 with any number of occurrences. The task was to find out two numbers A and B such that A and B doesn’t contain any occurrence of the digit 4 and summation of A and B should equal N(A+B=N).

So I thought of creating a new number let’s assume A for now, that would be same in length as N(length means number of digits in the number). The idea is while constructing the number A, we would analyze the number N digit by digit. For each occurrence of digit 4 in number N, we would add digit 1 in the number A. For rest of the digits in N, add digit 0 in the A. Following this, I got a number A.

I obtained the other number B by subtracting newly constructed A from N. And you see, I got two numbers A and B that do not contain digit 4 and the summation is equal to N.

For implementing this logic, I could not think of anything, but Python. The easy type conversions from integer to string or string to list and viz made it so easy to achieve this working.

Implementation

Code.

My View

This way it cracked all the test cases, no matter how large the input number was!

I believe the same logic can be implemented in various other languages, possibly the best in terms of time would be in C/C++, but Python just makes it super easy. You can switch from different data types with just few keywords and as you want.

I encourage any reader to try out this in some other language or in Python with less lines of code.

" The joy of coding Python should be in seeing short, concise, readable classes that express a lot of action in a small amount of clear code — not in reams of trivial code that bores the reader to death. "

-- Guido Van Rossum

Thanks for reading through. I welcome feedback and constructive criticism. I can be reached on Twitter @mistryvatsal11 or through my personal website mistryvatsal.github.io.