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.
The simple solution to this problem is to take each element of the array, and check how many element to the right of that element has a smaller ID. But, this will be too slow to get a 100%.
To solve this problem in a linear fashion, I instead calculate the offset the current element has to its starting position. I also work backwards through the array, and store the smallest value I've found so far. This leaves me with 4 cases for each element:
1. The offset is more than 2, so I print "Too chaotic" as more than 2 bribes have been used, and call return.
2. If the current element is smaller than the smallests value, I set it as the new smallest value.
3. If nothing else I add the offset to the number of bribes.
4. Finally the most tricky one, if an element has already been skipped by 1 or 2 elements, and that has left one element between those elements and the current element, and then the current element bribes the element in front of it, you get an offset of either 0 or -1, but its element is larger than the smallest value so far, so it should count as 1 bribe. It can't be 2 because then it would revert the bribe of one of the elements that bribed it initially, and the problem is to count the minimum number of bribes need to construct the current situation. Example of this is the number 6 in:
1 2 5 3 7 8 6 4
Here's my solution (C++):
voidminimumBribes(vector<int>q){intbribes=0;intlowest=q.back();for(inti=q.size()-2;i>=0;i--){intoffset=q[i]-(i+1);// if offset is too large, print "Too chaotic"if(offset>2){cout<<"Too chaotic"<<'\n';return;}elseif(q[i]>lowest&&offset<1){bribes+=1;}elseif(q[i]<lowest){lowest=q[i];}else{bribes+=offset;}}cout<<bribes<<'\n';}
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 →
The simple solution to this problem is to take each element of the array, and check how many element to the right of that element has a smaller ID. But, this will be too slow to get a 100%.
To solve this problem in a linear fashion, I instead calculate the offset the current element has to its starting position. I also work backwards through the array, and store the smallest value I've found so far. This leaves me with 4 cases for each element: 1. The offset is more than 2, so I print "Too chaotic" as more than 2 bribes have been used, and call return. 2. If the current element is smaller than the smallests value, I set it as the new smallest value. 3. If nothing else I add the offset to the number of bribes. 4. Finally the most tricky one, if an element has already been skipped by 1 or 2 elements, and that has left one element between those elements and the current element, and then the current element bribes the element in front of it, you get an offset of either 0 or -1, but its element is larger than the smallest value so far, so it should count as 1 bribe. It can't be 2 because then it would revert the bribe of one of the elements that bribed it initially, and the problem is to count the minimum number of bribes need to construct the current situation. Example of this is the number 6 in:
Here's my solution (C++):