20
\$\begingroup\$

I've recently stumbled upon a Russian site called acmp.ru, in which one of the tasks, HOK, asks us to find the LCM of two positive integers. The full statement, translated to English is as follows:

The only line of the input contains two natural numbers A and B separated by a space, not exceeding 46340.
In the only line of the output, you need to output one integer - the LCM of the numbers A and B.

On the Python leaderboard, the top solution is just 50 bytes, followed by a stream of 52s.

enter image description here

Note that the scoring method for this site is not standard, and uses the following formula:

max(code length without spaces, tabs and newlines, full code length divided by 4)

With this in mind, I have come up with two solutions that give a score of 52. One of them simply uses math.lcm, while the other one calculates it more directly:

from math import*
print(lcm(*map(int,input().split())))
a,b=map(int,input().split())
v=a
while v%b:v+=a
print(v)

Now I'm stumped. How can I save 2 bytes off my solution? (the Python version is 3.9.5).

\$\endgroup\$
15
  • \$\begingroup\$ could it be with python 2 ? \$\endgroup\$
    – MarcMush
    Nov 30, 2021 at 23:07
  • \$\begingroup\$ Is it counted in bytes or characters? \$\endgroup\$
    – hyper-neutrino
    Nov 30, 2021 at 23:15
  • 1
    \$\begingroup\$ But the top solution was written in July 2016, right? There was only Python 2 and Python 3 at that time. (Python 3.6 was apparently released in December.) \$\endgroup\$
    – Arnauld
    Nov 30, 2021 at 23:26
  • 1
    \$\begingroup\$ The 7.2 megabytes of memory used makes me think there's arithmetic generating-function-style tricks in play. Like, for gcd, there's gcd(a,b)==B**(a*b)//~-B**a%~-B**b%B some a large enough value B. \$\endgroup\$
    – xnor
    Dec 1, 2021 at 0:08
  • 3
    \$\begingroup\$ Actually, there is an 'lcm' in the numpy namespace, so that would be 44 tio.run/##K6gsycjPM/7/… \$\endgroup\$
    – loopy walt
    Dec 1, 2021 at 13:58

1 Answer 1

26
\$\begingroup\$

My solution to 50 bytes:

v=1
for x in input().split()*6**6:v+=-v%int(x)
print(v)

Explanation

The solution itself is relatively simple, but finding it was significantly more difficult.

First, note that the LCM of a and b is the smallest number v such that v%a==0 and v%b==0.

The main logic for this algorithm is in v+=-v%int(x). In a nutshell, it sets v to the first multiple of x greater than or equal to v. This means that if v%x==0, v doesn't change.

In a for loop, we repeat this process cyclically with both numbers. Whenever v is not divisible by x, v+=-v%x ensures that v becomes the immediate next divisor of x. This means that, at some point in the loop, v will equal the LCM. When it does, v will stop changing, since both numbers will be divisible by v.

To better illustrate the algorithm, here is an example on the input 36 27:

                v=1
(36): v+=-v%36; v=36
(27): v+=-v%27; v=54
(36): v+=-v%36; v=72
(27): v+=-v%27; v=81
(36): v+=-v%36; v=108
(27): v+=-v%27; v=108
(36): v+=-v%36; v=108
...

It remains to determine how many iterations are required. In the worst case, A and B are coprime, for which the LCM is A*B. For this, we would need exactly min(A,B) iterations. The statement tells us that both numbers are guaranteed to be at most 46340. We could simply use this number, but 6**6 is one shorter, and only does 316 extra operations.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.