Beautifull Array getting TLE can any one help?

Problem Link

My Solution Link

Obviously, you are getting TLE, because the complexity of your code is n^2.
Try to think a bit more tactfully. Look at this case:

2 4

Ask this question to yourself, can you ever make a beautiful array here?

2*4, you need 8 -> 2 4 8

now you need 16 and 32 -> 2 4 8 16 32

and it will grow infinitely.

Try to build up from this case. Think more and if you still don’t get an idea, ask and i’ll help more.

1 Like

You dont have to check product of every array number. O(N^2) solution is bound to get TLE. There is a simple and neat O(N) solution to it by observation.

Click to view

Hint 1: You only need to check what elements are contained in array and make cases.

Click to view

Hint 2: What if array has 2 or more elements with abs(arr[i])>1 ?? Will it be possible to have a beautiful array then?

Click to view

Hint 3: Explaining hint 2. Take array of {1,3,4}. ITs not beautiful since 3x4= 12 isnt here. Lets say we add 12. {1,2,3,4,12}. Still not beautiful because now 4x12=48 and 3x12=36 isnt present!! For any element you add, i can prove that maximum_arr[i] x any_arr[i]_such_that_abs(arr[i])_is_greater_than_1 is not present in array. Meaning, if there are atleast 2 elements with abs(Arr[i])>1, i can prove that array is not beautiful since it wont contain Maximum-element-in-array x Any-element-with-absolute-value-more-than-1 .

In other words, we can prove that any array with more than 2 elements with abs(arr[i])>1 is not beautiful.

Click to view

Hint 4: Take care of -1 !!!

Click to view

Hint 5, the elements to look out for are 1,0,-1

Click to view

Hint 6: An array of size=1 is beautiful by definition.

2 Likes
//