8
\$\begingroup\$

We define function D(x) as following:

D(x) = x + sum of digits of x + sum of prime factors of x then call x the father of D(x)

Write a program that gets input t at the first line and then gets an input in the next t lines. If that input had father, print YES otherwise NO

For example 12 is the father of 20
20 = 12 + (1 + 2) + (2 + 3)

preferably write a separate function for each of these tasks:

  1. Getting sum of the digits of a number
  2. Getting prime factors of a number
  3. Calculating D(x)

Notice that if you do lots of operations, you may get time limit error.

Time limit: 0.5 seconds
Memory limit: 128 MB

Input:
You get an input number t at the first line and then in the next t lines, you get number n for which you should solve the problem
enter image description here
Output:
Print the answer to each input in t lines.

Example:
Sample input:

2
4
20

Sample output:

NO
YES

I've written the code with python:

# function that returns the unique prime factors of number n as a list
def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    factors = list(set(factors))
    return factors


# function that returns the sum of digits of number n
def sum_digits(n):
    r = 0
    while n:
        r, n = r + n % 10, n // 10
    return r


# function to calculate the offspring of number X {D(X)}
def Offspring(X):
    DX = X + sum(prime_factors(X)) + sum_digits(X)
    return DX


ChildFather = {i: Offspring(i) for i in range(4, 1001)}
ChildFatherValues = list(set(list(ChildFather.values())))
ChildFather.clear()
Fathers = [i for i in ChildFatherValues if i <= 1000]
ChildFatherValues.clear()
t = eval(input())
for i in range(0, t):
    n = eval(input())
    if n in Fathers:
        print('YES')
    else:
        print('NO')  

I guess this part of code

ChildFather = {i: Offspring(i) for i in range(4, 1001)}
ChildFatherValues = list(set(list(ChildFather.values())))
ChildFather.clear()
Fathers = [i for i in ChildFatherValues if i <= 1000]
ChildFatherValues.clear()

is the bottle-neck for time limit. since I don't know how to find x by having D(x), I've solved the problem this way:

ChildFather = {i: Offspring(i) for i in range(4, 1001)}  

for numbers 4<= n<= 1000, I've created a dictionary {n:D(n)}

ChildFatherValues = list(set(list(ChildFather.values())))
ChildFather.clear()  

created a list of unique values of the dictionary and deallocated the memory used for the dictionary

Fathers = [i for i in ChildFatherValues if i <= 1000]
ChildFatherValues.clear()  

create a list of values smaller than 1000 and deallocated memory used for the original list

t = eval(input())
for i in range(0, t):
    n = eval(input())
    if n in Fathers:
        print('YES')
    else:
        print('NO')  

If a given number exists n in the final provided list, I understand that n can be written as D(m)=m+sum of digits of m + sum of prime factors of m so n has the father m and I'll print Yes otherwise NO
But seems that the program is not efficient.

  1. How can I measure the time consumed by this python program at run-time?
  2. How can I measure the memory consumed by this python program at run-time?
    (I'm new to python and am coding with sublime text 3 in Linux Ubuntu)
  3. Is there any more efficient way of writing the code?
\$\endgroup\$
  • 1
    \$\begingroup\$ Do you have the challenge source/link? \$\endgroup\$ – Ludisposed Sep 17 '18 at 12:56
  • 2
    \$\begingroup\$ @Ludisposed Yeah, here it is. But it's in Persian. In fact it's not a challenge. This is an Iranian website to practice programming and this question was a homework passed to students of Sharif University of Iran 3 years ago in fall 2015. Now the question is for the people to practice. \$\endgroup\$ – Sepideh Abadpour Sep 17 '18 at 14:47
  • 1
    \$\begingroup\$ I struggled with the terminology a bit. I think it's a little more conventional in English to call x the root of D(x), in case that helps anyone else reading this. Otherwise, great question, and welcome to Code Review! \$\endgroup\$ – Toby Speight Sep 18 '18 at 9:42
6
\$\begingroup\$

PEP-8

Try to stick to PEP-8. So snake_case for variable and method names and a lot of other guidelines. Check any other Code Review Python post for tips from people who can explain this better than me.

Memory

Since you have 128MB of memory available, and a list of 1000 integers (l = list(range(1000)); sys.getsizeof(l) + sum(map(sys.getsizeof, l))) takes only 37kb on my system, I would not worry about clearing intermediate results.

Pre-calculate the primes to 1000

If the input number never goes beyond 1000, pre-calculating all the primes will be the fastest and most efficient. Here is method rwh_primes from this SO post adapted for Python 3:

def primes(n):
    # https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    """ Returns  a list of primes < n """
    sieve = [True] * n
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i]:
            sieve[i * i :: 2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
    return [2] + [i for i in range(3, n, 2) if sieve[i]]

This takes about 50µs on my PC.

prime_factors

You do some of unnecessary calls to set and list. I would implement this as a generator, and store it further upstream as a set:

def prime_factors(n):
    for factor in PRIMES:
        if factor > n**.5:
            yield n
            return
        while not (n % factor): # n is divisible by factor
            yield factor
            n //= factor
            if n == 1:
                return

sum_digits

This one looks okay. You could use divmod, but that is a matter of taste.

offspring

No need for the intermediate DX:

def offspring(x):
    return x + sum(set(prime_factors(x))) + sum_digits(x)

Main guard

Keep the main logic behind a if __name__ == '__main__': guard.

eval

Instead of using eval, since you know it will be int, better use int(). eval can be dangerous, since it can execute arbitrary code. If you need to interpret a python literal, use ast.literal_eval.

Then you do something very inefficient by creating a dict, then take only the values, apply list, set and list again. Easiest would be to just use a set-comprehension:

all_offspring = {offspring(i) for i in range(1, 1001)}

This will include some numbers over 1000, but this extra memory should be negligible.

Test

You can spoof input on your system by something like

test_case = '''2
4
20'''
input = iter(test_case.split('\n')).__next__

main

if __name__ == '__main__':
    PRIMES = primes(1000)
    all_offspring = {offspring(i) for i in range(1, 1001)}
    t = int(input())
    for i in range(t):
        n = int(input())
        if n in all_offspring:
            print('YES')
        else:
            print('NO')

Timing

To time it you can use timeit module. There are enough posts on SO about this, and for memory usage.

\$\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.