3
\$\begingroup\$

Here's the cool number problem given to me by my senpai in competitive programming:

A cool number is a number that can be at the same time written as the square of a whole number and the cubic of another whole number.
Write a program in Python that returns the number of cool numbers for every given [m, M] with 1 <= m < M <= 10^9
Input data: m and M 2 integers
Output format: the number of cool numbers in [m, M]
Time execution limit: 1 second
Memory space limit: 64 Mo

First I naively thought about testing for each number between m and M, but that took more than 10 seconds just for values between 1 and 10e6.
But as I was thinking about a way to check if the output is correct, I thought about having a maximum of roots, lets say if there were 64 numbers in the [1, 64] range, the sixth root of that range would have 4 numbers in [1, 4], that's when it hit me, I can simply have the sixth root of my range and those are the roots of my cool numbers, I just have to count them and raise them to the power of 6 if I want to know what my cool numbers are. So yeah here's my code that does exactly that, while also checking for execution time, I'll check for how much space it takes later

from time import perf_counter
from personalMath import root, ceil, floor

# input and declaring variables
m, M = [int(float(x)) for x in input().split()]
sixthm = floor(root(m, 6, 10))
sixthM = ceil(root(M, 6, 10))
counter = 0

# magic
t1 = perf_counter()
n = sixthM - sixthm + 1
t2 = perf_counter()

for x in range(sixthm, sixthM + 1):
    print("Cool number {}: {}".format(x, x**6))

t3 = perf_counter()
findTime = t2 - t1
printTime = t3 - t2
findAndPrintTime = t3 - t1

# output
print("There are {} cool numbers between {} and {}".format(n, m, M))
print("Finding time: ", findTime)
print("Printing time: ", printTime)
print("Total execution time: ", findAndPrintTime)

and here are my functions

def root(x, n, m):
    return round(x**(1/n), m)


def floor(n):
    return int(n//1)


def ceil(n):
    return int((n//1) + 1)

If you could give me your thoughts, I'd highly appreciate it!

\$\endgroup\$
2
  • \$\begingroup\$ Please do not edit the question, especially the code, after an answer has been posted. Changing the question may cause answer invalidation. Everyone needs to be able to see what the reviewer was referring to. What to do after the question has been answered. You can write a follow up question that points back to this question. \$\endgroup\$
    – pacmaninbw
    Jan 29, 2022 at 12:49
  • \$\begingroup\$ @pacmaninbw sorry for the trouble! I'll try to avoid that in the future \$\endgroup\$
    – Epsilon
    Feb 4, 2022 at 10:15

2 Answers 2

1
\$\begingroup\$

Using the math module

One way to improve the speed is to use the math builtin module:

from math import ceil, floor, sqrt

(Will add more later on.)

\$\endgroup\$
0
\$\begingroup\$

Congratulations, you're using the best algorithm possible (\$O(1)\$) for this task. Only small optimizations are available, and they aren't needed because 1 second and 64MB are much over your needs here.

Input data: m and M 2 integers

You're reading input as floats and convert them into integers. Why? For number under 1e9 it does nothing (except for spending extra time and code), but for 1e20 there will be precision losses. Just read ints as stated in the task.

Output format: the number of cool numbers in [m, M]

You output much more data than needed. Code is usually checked by automated systems, and your code will fail such checks. Also, your code doesn't work as intended: it says 3 numbers in [1,64], but there are only 2 (1 and 64).

Native functions are better (faster and more correct) in most cases. You should have a good reasoning (like clearly stated "don't use the math module") to not use them. There's timeit module to check execution times.

Create a function, say cool_number, and put your code into it. This way, you'll be able to pass this function to timeit.

You're calculating time for one line only; but finding sixthm and sixthM is also the part of the algorithm, you should account that time too.

\$\endgroup\$
1
  • \$\begingroup\$ Honestly I just I read them as floats and convert them for the convenience of writing 1e9 in the input "Your code doesn't work as intended" indeed my math functions are wrong if the number is already an integer! It would give the value +1 "Native functions are better" since I am just practicing right now, I'd rather try to create everything from scratch, but you're right usually I'd just use the Math module for ceil/floor and NumPy for the roots! "You're calculating time for one line only" You're right, I'll try with timeit this time Thanks you very much for all your valuable input! \$\endgroup\$
    – Epsilon
    Jan 28, 2022 at 15:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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