Help me in solving POWPM problem

help
,
1

My issue

I am getting time limit error, is there a way to increase this codes speed?

My code

# cook your dish here
def pairs(arr, a,n):
	if a == 1:
		return n
	c = 0
	for i in range(n):
		if (a**(i+1)) <= arr[i]:
			c+=1
	return c
		
for _ in range(int(input())):
    n=int(input())
    arr = [int(x) for x in input().split()]
    x=[]
    for i in arr:
        x.append(pairs(arr,i,n))
    print(sum(x))

Problem Link: Powered Parameters Practice Coding Problem - CodeChef

2

@anuskcse
plzz refer my c++ code for better understanding of the logic

#include <bits/stdc++.h>
using namespace std;

int main() {
	// your code goes here
	int t;
	cin>>t;
	while(t--)
	{
	    long long int n;
	    cin>>n;
	    long long int a[n],ans=0;
	    for(int i=0;i<n;i++)
	    {
	        cin>>a[i];
	    }
	    for(int i=0;i<n;i++)
	    {
	        if(a[i]==1)
	        ans+=n;
	        else
	        {
	            long long int val=1;
	            for(int j=0;j<min(32LL,n);j++)
	            {
	                val*=a[i];
	                if(val>1e9)
	                break;
	                if(val<=a[j])
	                ans++;
	            }
	        }
	    }
	    cout<<ans<<endl;
	}
	return 0;
}
3

Since, n is the large integer, we cant run n ** 2 times, which could lead to Time Limit Exceeded error. So, we have to optimize the code. (By running lesser than n times each)

4

I don’t know c++

5

Can’t understand
for(int j=0;j<min(32LL,n);j++)
And
if(val>1e9)
Lines

6

@anuskcse
for loop runs till minimum value of (32 and n)
and val > 1e9 means val > 1000000009

7

@dpcoder_007
is it possible to do the same in python

8

@anuskcse
yes ofcourse