For a chat application, a team of developers needs to study the different message writing patterns of the users. Some users write long messages and some users write short messages. As a part of the study the developers have a sequence of lengths of N messages in their system in the order in which these were sent in a chat by the users. The developer must select a homogenous sequence such that the maximum length of a message is less than double the minimum length of a message in the selected sequence. For selection, only the messages from one of the ends of the sequence can be removed. The system must remove the minimum number of messages while fulfilling the developer's requirement.
Write an algorithm to find the minimum number of messages that must be removed so that the maximum length of a message is less than double the minimum length of a message in the final selected sequence.
Input
The first line of the input consists of an integer-msglist size representing the number of selected messages from a chat (N)
The next line consists of N space-separated integers — msgList[0], msgList[1] .....msgList[N-1], representing the length of messages,
Output
Print an integer representing the minimum number of messages that must be removed after selecting a sequence such that the maximum length of a message is less than double the minimum length of a message in the selected sequence.
Constraints
0<=msglist_size<=10^4
0<msgList[0], msgList[1] ,......msgList[N-1)<1000
Example
Input:
5
22 5 4 7 15
Output
2
Since the size of the message is <= 1000, you can brute force the answer by picking the minimum length of a message from 1 to maximum length of a message and select the most optimum one i.e. the one which requires the less number of removal.
Let's say you fixed the minimum length of the message as
tso all the messages who's size is less thantor greater than2tmust be removed. There could bemways of doing wheremis the number of such points . So the expected time complexity will beO(messageLength*messageListSize)I think your approach is O(n^2) approach, do you have any better optimised approach, do share.
You can do it in n log n as well, with sorting and binary search. You iterate through the smallest T messages, trying to remove them. Then, you know exactly which max values are too big, with a binary search (lower bound on the sorted array). Overall complexity is O(n log n)
Great, if you like, could you elaborate your logic bit more, I know binary search but i am not well verse with it. If you could state the logic more, it would be great help for me.