DhruvBohara's blog

By DhruvBohara, history, 6 months ago, In English

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

  • Vote: I like it
  • -4
  • Vote: I do not like it

»
6 months ago, # |
  Vote: I like it +13 Vote: I do not like it

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 t so all the messages who's size is less than tor greater than 2t must be removed. There could be mways of doing where m is the number of such points . So the expected time complexity will be O(messageLength*messageListSize)