Loudspeakers

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
34 upvotes
Asked in companies
DunzoDirecti

Problem statement

The famous cultural festival of your locality is near and as a member of the committee, you are given the responsibility of arranging loudspeakers for the cultural festival that has to take place. Now, you have arranged N loud-speakers where the ith loudspeaker has loudness or amplitude LOUD[i]. Now when one loudspeaker of loudness Y is kept with another loudspeaker of loudness X, the combined loudness is expressed as Y^X.

So, when N loudspeakers are kept in order A1, A2, A3……….An, the combined loudness will be (A1^(A2^(A3^(...........(An))))). So, your task is to rearrange the loudspeakers such that the combined loudness emitted is maximum.

Example:- 
Let, 
N = 3
LOUD = [4, 5, 6]
Answer:- [4, 5, 6]
Explanation:- The answer should be 4,5,6 because out of all the rearrangements that are possible the array [4,5,6] will emit the largest combined loudness. Arrangement 4,5,6 emits an amplitude of 4^5^6 (1152921504606846976) and arrangement 6,5,4 emits an amplitude of 6^5^4 (3656158440062976).
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ representing the number of test cases. Then each test case follows.

The first line of each test case contains an integer ‘N’ denoting the number of loudspeakers you have.

The third line contains ‘N’ integers of the array ‘LOUD’ denoting the loudness of the speakers.
Output Format : 
For each test case, print ‘N’ integers denoting the lexicographically smallest rearrangement of loudspeakers such that they emit the largest combined loudness.

The output of each test case should be printed in a separate line.
Note : 
You are not required to print anything, it has already been taken care of. Just implement the function.
Constraints : 
1 <= T <= 5
1 <= N <= 10^5
1 <= LOUD[i] <= 10^9

Note:- Loudspeakers having an amplitude of more than 1 will all have unique amplitudes.

Time Limit = 1 sec
Sample Input 1 :
2
2
2 3
2
2 4
Sample Output 1 :
3 2
2 4
Explanation for Sample Output 1 :
In the first test case, the answer should be 3, 2 because 3, 2 emits a loudness of 9 which is the maximum possible.
In the second test case, the answer should be 2, 4 because 2, 4 emits a loudness of 16 which is the largest possible. (Note that 4, 2 also yields the same output but 2, 4 is lexicographically smaller).
Sample Input 2 :
1
1
7
Sample Output 2 :
7
Hint

Try keeping loudspeakers with low amplitude first.

Approaches (1)
Greedy

We can observe that we have to keep the loudspeakers with amplitude at last as 1 raised to the power is 1 so we take out all the ones separately. Now, the key observation is x^y is always greater than y^x when x<y. The only exception to this is when x=2 and y=3. So, we treat the corner case [2,3] separately, else we print the array in ascending order. 

 

Algorithm:-

 

  1. Initialize an array named ANS to store the rearrangement which gives the maximum combined loudness.
  2. Initialize 2 empty arrays named ONES and ANS_WITHOUT_ONES.
  3. Iterate from 0 to N(Let’s say the iterator be i).
    1. If LOUD[i] is 1, add 1 to ONES.
    2. Else, add LOUD[i] to ANS_WITHOUT_ONES.
  4. Else, update ANS_WITHOUT_ONES as ANS_WITHOUT_ONES sorted in ascending order.
  5. If ANS_WITHOUT_ONES is equal to [2,3], update ANS_WITHOUT_ONES [3,2].
  6. Update ANS as ANS_WITHOUT_ONES plus ONES.
  7. Return ANS.
Time Complexity

O(N * log N), where N is the number of loudspeakers.

We are sorting ‘N’ loudspeakers, so the time complexity is O(N * log N).

Space Complexity

O(N), where N is the number of loudspeakers.

We are using an auxiliary array to sort ‘N’ loudspeakers in ascending order, so the space complexity is O(N).

Code Solution
(100% EXP penalty)
Loudspeakers
Full screen
Console