How to optimize This Algorithm

Question is
Chef is attending math classes. On each day, the teacher gives him homework. Yesterday, the teacher gave Chef a sequence of positive integers and asked him to find the maximum product of two different elements of this sequence. This homework was easy for Chef, since he knew that he should select the biggest two numbers.

However, today, the homework is a little bit different. Again, Chef has a sequence of positive integers A1,A2,…,AN

, but he should find two different elements of this sequence such that the sum of digits (in base 10

) of their product is maximum possible.

Chef thought, mistakenly, that he can still select the two largest elements and compute the sum of digits of their product. Show him that he is wrong by finding the correct answer ― the maximum possible sum of digits of a product of two different elements of the sequence A

.

Input

  • The first line of the input contains a single integer T

denoting the number of test cases. The description of T* test cases follows.

  • The first line of the input contains a single integer N

  • .

  • The second line contains N
    space-separated integers A1,A2,…,AN

  • .

Output

For each test case, print a single line containing one integer ― the maximum sum of digits.

Constraints

  • 1≤T≤100

  • 2≤N≤100

  • 1≤Ai≤104
    for each valid i

Subtasks

Subtask #1 (100 points): original constraints

Example Input

3
2
2 8
3 
8 2 8
3
9 10 11

Example Output

7
10
18

My Code is as follows …
Please suggest optimization in THE algorithm of my code.

def partition(arr,low,high):
i = ( low-1 )
pivot = arr[high]

for j in range(low , high): 

   
    if   arr[j] <= pivot: 
      
      
        i = i+1 
        arr[i],arr[j] = arr[j],arr[i] 

arr[i+1],arr[high] = arr[high],arr[i+1] 
return ( i+1 ) 

def quickSort(arr,low,high):
if low < high:

    pi = partition(arr,low,high) 

    
    quickSort(arr, low, pi-1) 
    quickSort(arr, pi+1, high) 

T=int(input())
for i in range(1,T+1):
cf=[]
N=int(input())
A=list(map(int,input().split()))
if(len(A)==N):
for k in range(len(A)):
z=k+1
for j in range(z,len(A)):
p=A[k]*A[j]
m=p
s=0
while(m!=0):
d=m%10
s=s+d
m=m//10
cf.append(s)
quickSort(cf,0,len(cf)-1)
print(cf[-1])

Problem Code —>RPD
and Problem Name---->Easy Math

bro you dont need you copy and paste whole statement of the question just drop a link .
like this https://www.codechef.com/LTIME74B/problems/RPD/ and format your code .

and i dont know python so i suggest you to take a look at the accepted solutions and learn from them .
https://www.codechef.com/status/SUBINC?sort_by=All&sorting_order=asc&language=116&status=15&handle=&Submit=GO

Bruh i am getting the output correctly in my machine but on the Online IDE i encounter TLE
I mean My solution is Partially Accepted…

online ide is not same as your system to run for such a long time . optimise your algorithm then .

refer to accepted solutions bro

Thats the thing in which i wanted help…:slightly_smiling_face:

Have You answered It Correctly??

as i said earlier . i dont code in python i code in c++

so bro have you coded the solution correctly in c++

yes, you can visit my profile

Thank you so much:slightly_smiling_face:

slighty smiling lol.

I don’t code in Python too but I guess a simple bruteforce would be okay. You’re quicksorting the array (not needed) and then appending elements (very expensive function). Just multiply every element with all the next elements and store the maximum sum of digits of the products you encounter. I did this and got AC.
Ref: https://www.codechef.com/viewsolution/25446690

I’ll try to code a solution in Python and revert back to you. : slightly_smiling_face :

UPDATE: I just used the same algorithm I used in C++ and coded it in Python and apparently I got TLE lol.
Ref: https://www.codechef.com/viewsolution/25488057

However, this solution is same and got AC.
Ref: https://www.codechef.com/viewsolution/25487900

Maybe I need to learn the Pythonic ways.

Just make the division by 10 an integer division. In Python 3 you should use n //=10 instead of n /= 10

1 Like

Constraints are too loose so brute force will work.

  1. Format your code whenever you ask…
  2. I guess brute force will work

Always paste the problem link and your submission link. It’s much easier to go through and understand the problem and your approach. Anyways, I went through your answer and I don’t understand why are you performing quicksort. The solution is a complete brute force and implementation.
If you want any help, you can check my solution. It’s in python.
RPD submission