New Year Chaos HackerRank solution in Java
It is New Year's Day and people are in line for the Wonderland rollercoaster ride. Each person wears a sticker indicating their initial position in the queue. Initial positions increment by 1 from 1 at the front of the line to n at the back.
Any person in the queue can bribe the person directly in front of them to swap positions. If two people swap positions, they still wear the same sticker denoting their original places in line. One person can bribe at most two others. For example, if n=8 and person5 bribes person4 the queue will look like this: 1,2,3,5,4,6,7,8.
Fascinated by this chaotic queue, you decide you must know the minimum number of bribes that took place to get the queue into its current state. If anyone has bribed more than two people, the line is too chaotic to compute the answer.
See full description in HackerRank :-
Solution 1
public class NewYearChaos {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Enter array size");
int number = sc.nextInt();
int[] array = new int[number];
System.out.println("Enter array values");
for (int i = 0; i < number; i++) {
array[i] = sc.nextInt();
}
for (int i = 0; i < array.length; i++) {
if ((i+2 < array.length) && (array[i] - i) > 3) {
System.out.println("Too chaotic");
return;
}
}
int totalCount = 0;
for (int i = array.length-1; i >= 0; i--) {
for (int j = Math.max(0, array[i] - 2); j < i; j++) {
if (array[j] > array[i]) {
totalCount++;
}
}
}
System.out.println(totalCount);
}
}
Output :-
Enter array size
8
Enter array values
1 2 5 3 7 8 6 4
7
---------------------
Enter array size
8
Enter array values
5 1 2 3 7 8 6 4
Too chaotic
Solution 2
import java.util.Scanner;
public class NewYearChaos {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Enter array size");
int number = sc.nextInt();
int[] array = new int[number];
System.out.println("Enter array values");
for (int i = 0; i < number; i++) {
array[i] = sc.nextInt();
}
int totalSwap = 0;
for (int i = array.length-1; i>0 ; i--) {
if (array[i] != i+1) {
if (((i - 1) >= 0) && array[i - 1] == (i + 1)) {
totalSwap++;
swap(array, i, i - 1);
} else if (((i - 2) >= 0) && array[i - 2] == (i + 1)) {
totalSwap += 2;
swap(array, i - 2, i - 1);
swap(array, i - 1, i);
} else {
System.out.println("Too chaotic");
return;
}
}
}
System.out.println(totalSwap);
}
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
Other HackerRank Problem and Solution :-
Comments
Post a Comment