Find count of possible power of the given element-CodePudding

You are given an array A having N integers. An element X in A is called perfect if X can be written as Y**Z for any Y >0 and Z>1

1<= N <= 10^5
1<= A[i] <= 10^5

Input:

2
9
6

Output

9 can be written as 3^2

def solve(N,A):
    count=0
    for i in A:
        for j in range(1,int(i)//2):
            for k in range(1,int(j):
                if j**k == int(i):
                    count=count 1
                    i = i   1
    return count

This approach gives me correct answer for any type of input in my system unless it is in competitive coding IDE The error message read Time Limit Exceeded How do I overcome this problem ?

CodePudding user response：

You can try simple preprocessing. First of all, based on limits you need to check approximately n * 20 numbers (because 2 ** 20 > N), so it's O(n) - good, next when you processed all possible numbers you can simply compare your input with preprocessed data as follows:

def solve(n, a):
    MAXN = 10 ** 5   1
    is_perfect = [False] * MAXN

    for number in range(1, MAXN):
        for power in range(2, 20):
            if number ** power > MAXN:
                break
            is_perfect[number**power] = True

    counter = 0

    for element in a:
        if is_perfect[element]:
            counter = counter   1

    return counter

Final complexity is O(n)