TLE in question: Sort array according to number of set bits

#1

2481c0fb-8017-4e6a-a466-2f99840f6d9f.jpg954×2460

I have given you the problem details, including it’s sample input and output, constraints etc.

The code that I wrote for this problem is:

However, on submitting, it just passes 8/10 test cases and shows Time Limit Exceeded on other test cases. I firstly wanted to ask that why do I get this TLE and secondly, can you help me optimize the time complexity of this code, such that I don’t give the Time Limit Exceeded message?

#2

try submitting https://ide.codingblocks.com/s/588632
if u still face any issue msg back here

#3

Vaibhav sir, I submitted your code, it is still giving me Time Limited Exceeded on 2/10 testcases. Kindly do some changes to reduce the time complexity of the algorithm.

#4

can u share the snippet of ur submissions… bcoz in my account its getting submitted successfully

#5

Capture

Please find any optimised solution to this.

#6

Sir I request you to kindly go through the constraints of the problem again and optimize the code according to constraints.

#7

okay … let me see…

#8
  • Maintain a Multimap to store the pair of integer and its set bit count.
  • The trick is to make (-1*count of set bits) as the key of the map because we have to sort the array on the basis of the count of set bits and it is multiplied by -1 because we have to sort it in descending order and by default the multimap store the integers in ascending order.
  • Now traverse the map from the beginning and store all the elements in the array and return this array as the answer.

try this https://ide.codingblocks.com/s/588995 it should work

#9

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#10

Sir your solution is getting accepted correctly, but I wanted to know how about how did you traverse the multimap:

You have written this code for traversing:

for (auto j : result)

{
    arr.push_back(j.second);
}

I had some doubts regarding this:

  1. Why are we using auto j and result to traverse the multimap, and how do they work?
  2. Why do I need to specify auto keyword? I mean, by default, all variables are auto, so if I simply write j instead of auto j, will it work fine?
  3. What is the time complexity involved in traversing a multimap?
  4. Can I use an unordered map instead of multimap for doing the same question?
  5. Also, what was the motivation/reasoning behind using multimaps in this question?
#11

Hi… so basically auto is just an iterator used for traversing… u must have read about it or will learn in further videos. Coming on to complexity of traversing a multipmap in O(N)
I used multimap because there can be same key values

1 Like