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.
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);
if(bribedPosition>2){
System.out.println("Too chaotic");
return;
}
if(bribedPosition>0){// Add bribe since its given bribe
bribe+=bribedPosition;
}
if(bribedPosition==2){
++doubleBribeCnt; // track double bribe count
} else if(bribedPosition<=0&&doubleBribeCnt>0){ // bribedPosition is negative means the person is receiver
// what if the bribe receiver has bribed one single time case!!!
if((doubleBribeCnt ==1&&bribedPosition==0)||(doubleBribeCnt-1==-1*bribedPosition)){
bribe++;
}
doubleBribeCnt=0; // reset double bribe count upon sensing a bribe receiver
}
}
System.out.println(bribe);
}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
New Year Chaos
You are viewing a single comment's thread. Return to all comments →
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);
}