+ 1

How can I optimise the solution to avoid TLE

Given an array AA consisting of NN integers A1,A2,…,ANA1,A2,…,AN, determine if you can sort this array by applying the following operation several times (possibly, zero): Pick a pair of indices (i,j)(i,j) with i≠ji≠j and Ai&Aj≠0Ai&Aj≠0, and swap the values of AiAi and AjAj. Here, && denotes the bitwise AND operation. For example, if A=[6,4,2]A=[6,4,2], the two possible operations are (1,2)(1,2) and (1,3)(1,3). (2,3)(2,3) cannot be performed because A2&A3=4&2=0 I developed a very naive solution to this problem, which gives TLE for large inputs. Can someone please help me optimize the code. A fresh approach is also welcome :)

12th Feb 2022, 12:56 PM
sanjit jha
sanjit jha - avatar
1 Answer
I could be wrong, but if this works like a bubble sort then you could optimize the loop ranges like this: for i in range(x-1): for j in range(i+1,x):
13th Feb 2022, 6:13 PM
Brian - avatar