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
|
71 Discussions
|
Please Login in order to post a comment
pyhton 3
Javascript
It's essentially a reverse insertion sort. You just keep looping through the array doing a single swap until it's sorted. Count how many times you had to make a swap to get it sorted. Break if the value of any element is more than two higher than its original position.
Here is HackerRank New year chaos problem solution in Python, java, C++, C and javascript
Can't shake the feeling that other solutions and explanations are just too complicated.
Observations: - This is a que of people, normally always starts 1,2,3,4... - Since person can skip at most 2 positions, it means that if we look at que segment of size 3, we known that for arbirary position i only i, i+1 and i+2 can be there - So for initial segment [p1,p2,p3] at position p1 can only be 1 (the original), 2 (if it bribed) or 3 (if it bribed twice)
So if normally the queue was supposed to start with [p1, p2, p3] = [1, 2, 3] , then by scanning the queue from left to right (via var x) and keeping track of p1, p2, p3 we can encounter the following cases
1) x == p1 // x is at it's place and did not bribe anyone
p1, p2, p3 = p2, p3, p3+1 // shift the window to the right
2) x == p2 // x bribed once and skipepd 1 ahead bribes += 1 p2, p3 = p3, p3+1 // expected p1 is the same, p2 and p3 move to the right
3) x == p3 // x bribed twice and skipped 2 ahead bribes += 2 p3 = p3+1 // we are still expecting the same p1 and p2, p3 moves to the right
4) x is outside the window thus it's chaos
Code in golang
Java