Follow

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use
Contact

How does this seemingly random bit of string solve the TwoSum problem?

From LeetCode, the definition of the "Two Sum Problem" is:

Given an array of integers nums and an integer target, return indices
of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and
you may not use the same element twice.

MEDevel.com: Open-source for Healthcare and Education

Collecting and validating open-source software for healthcare, education, enterprise, development, medical imaging, medical records, and digital pathology.

Visit Medevel

You can return the answer in any order.

Example 1:

nums = [2,7,11,15]

target = 9

Output: [0,1]

The current solution on LeetCode with the fastest runtime on Python is the following:

class Solution(object):
    def twoSum(self, nums, target):
        from zlib import decompress
        from base64 import b64decode
        open('user.out', 'wb').write(decompress(b64decode("eJyLNtRRMIjlijbSUTAEUggekqAxiqCJjoIRhgZjFEGESgMMJVDtphDKGK7SGKFy2FKwAAFyTRGilkCgowAkLIAcMx0IaQmSN9IxAqsz0zE0B9IGOsDABQCpFVmV"))),exit(0)

From my perspective, I have no idea how this code would be generated. It seems like they taking an advantage of a vulnerability in the interpreter, but even that isn’t clear.

How exactly does this script run and how does it perform the actions noted above in the problem description?

>Solution :

Base64 allows to encode binary data as text, which then is decompressed

from zlib import decompress
from base64 import b64decode
print(decompress(b64decode("eJyLNtRRMIjlijbSUTAEUggekqAxiqCJjoIRhgZjFEGESgMMJVDtphDKGK7SGKFy2FKwAAFyTRGilkCgowAkLIAcMx0IaQmSN9IxAqsz0zE0B9IGOsDABQCpFVmV")))

gives output

b'[1, 0]\n[2, 1]\n[1, 0]\n[2, 0]\n[2, 1]\n[3, 0]\n[2, 0]\n[4, 2]\n[2, 1]\n[1, 0]\n[3, 2]\n[2, 1]\n[2, 0]\n[4, 0]\n[1, 0]\n[3, 2]\n[4, 2]\n[5, 2]\n[3, 0]\n[4, 3]\n[1, 0]\n[1, 0]\n[1, 0]\n[1, 0]\n[1, 0]\n[1, 0]\n[1, 0]\n[1, 0]\n[1, 0]\n[1, 0]\n[1, 0]\n[1, 0]\n[1, 0]\n[1, 0]\n[1, 0]\n[1, 0]\n[1, 0]\n[1, 0]\n[1, 0]\n[1, 0]\n[1, 0]\n[1, 0]\n[1, 0]\n[1, 0]\n[1, 0]\n[1, 0]\n[1, 0]\n[1, 0]\n[1, 0]\n[1, 0]\n[1, 0]\n[1, 0]\n[4, 0]\n[11, 5]\n[1, 0]\n[9999, 9998]\n[6,8]\n[6,9]\n[12,25]\n[16,17]\n[0,1]\n'

so author just stored expected output and is then writing it to user.out which I presume is then tested by judge.

Add a comment

Leave a Reply

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use

Discover more from Dev solutions

Subscribe now to keep reading and get access to the full archive.

Continue reading