We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
- New Year Chaos
- Discussions
New Year Chaos
New Year Chaos
Sort by
recency
|
250 Discussions
|
Please Login in order to post a comment
I realized you need to keep track of what's not found, after spending a long time trying to solve this. Once you find something you remove it from the not found list. If you go past 2 in not found trying to match, it's too many bribes.
Problematic question, which the writers probably didn't really thought through. Let's have a look at the example that they gave: q = [4,1,2,3]. The problem description suggests that this would be "TOO CHAOTIC". But it is not, 1 would bribe 4 to get to its original position and the new queue would be q = [1,4,2,3]. Then 2 and 3 would do exactly the same in the respective order and everybody would be in their position. There would occur 3 bribes and everybody would be in their position. So what are the actual rules to do the bribing? I believe this question is faulty and needs some new rules to be introduced.
Timing out on 4 cases :
def minimumBribes(q): n = len(q)
O(n) Complexity
Interesting Properties found in bribed queues & about hidden bribe
Example of hidden bribe
I/P: 1 2 5 3 7 8 6 4
Bribes : 7
5 - 2 times
7 - 2 times
8 - 2 times
6 - 1 time // possible hidden bribe
Properties
The bribed person minus the index position gives the bribe given (assume index start from 1)
ONLY ONE Hidden bribe can occur after one or more double bribe takes place
To find hidden bribe:
After every Nth Hidden bribe, if the next person moved -N postion, he didnt bribe else a bribe happened (i.e., (DoubleBribe Count -1) = -1 * bribes taken)
Note: we reset double bribe count upon reaching a person who received a bribe. Person who received a bribe can be decided if [The bribed person - the index position is negative]
Code:
public static void minimumBribes(List q) { int doubleBribeCnt=0;
int bribe=0;
for(int i=0;i // get the bribed position, given or taken // Given: positive | Received: negative int bribedPosition=q.get(i)-(i+1);
}
the official solution for python also fails the time limit requirements. Amazing. does anyone have a working solution?