Larry's array hackerrank solution in python
|
Larry has been given a permutation of a sequence of natural numbers incrementing from 1 as an array. He must determine whether the array can be sorted using the following operation any number of times: For example, if : A rotate
[1,6,5,2,4,3] [6,5,2]
[1,5,2,6,4,3] [5,2,6]
[1,2,6,5,4,3] [5,4,3]
[1,2,6,3,5,4] [6,3,5]
[1,2,3,5,6,4] [5,6,4]
[1,2,3,4,5,6]
YES
On a new line for each test case, print YES if A can be fully sorted. Otherwise, print NO. Read more on the challenge page…
I’m providing the solution for Python and JS, please leave on the comments if you found a better way. That I could think of, there are 2 approaches to solve this problem. The first one being the obvious, doing all the permutations and evaluating at the end when 2 items are left if they are in order. The other way, which happens I knew it already, has to do with inversion
. Inversions are particularly interesting for this problem. Now if you don’t know about inversions, is very unlikely to find this solution on your own. By definition, The inversion number is the cardinality of inversion set. It is a common measure of the sortedness of a permutation or sequence. What’s an interesting property of the inversion number is that the order of the permutation won’t actually affect its even/odd nature for the entire array. Here is that demonstrated with a few examples: Example 1: 312 inversion(312) = 2 312 -> 123 = sorted! Example 2: 231 inversion(231) = 2 231 -> 312 -> 123 = sorted! Example 3: 213 inversion(231) = 1 213 -> 132 -> 321 -> 213 != can't be sorted So we can say that only those combinations with even inversion number can be sorted, and that’s what we are going for. Larry has been given a permutation of a sequence of natural numbers incrementing from 1 as an array. He must determine whether the array can be sorted using the following operation any number of times: Choose any 3 consecutive indices and rotate their elements in such a way that ABC->BCA->CAB->ABC. For example, A = {1,6,5,2,4,3} : On a new line for each test case, print YES if A can be fully sorted. Otherwise, print NO. Function Description Complete the larrysArray function in the editor below. It must return a string, either YES or NO. larrysArray has the following parameter(s): Input Format The first line contains an integer t, the number of test cases. The next t pairs of lines are as follows:
Output Format For each test case, print YES if A can be fully sorted. Otherwise, print NO. Sample Input 3 3 3 1 2 4 1 3 4 2 5 1 2 3 5 4Sample Output YES YES NOLarry’s Array HackerRank Solution in C#includeLarry’s Array HackerRank Solution in C++#includeLarry’s Array HackerRank Solution in Javaimport java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { static int[] aux; public static long insertSort(int[] ar) { aux = new int[ar.length]; long count = mergeSort(ar, 0, ar.length-1); return count; } public static long mergeSort(int[] ar, int from, int to) { long count = 0; if (from + 8 >= to) { for (int i = from+1; i <= to; i++) { int x = ar[i]; int j = i-1; while (j >= from && ar[j] > x) { ar[j+1] = ar[j]; count++; j--; } ar[j+1] = x; } return count; } int middle = (from + to) / 2; count += mergeSort(ar, from, middle); count += mergeSort(ar, middle+1, to); count += merge(ar, from, middle+1, to); return count; } public static long merge(int[] ar, int from, int second, int to) { long count = 0; for (int i = from; i <= to; i++) { aux[i] = ar[i]; } int i = from; int j = second; int k = from; while (k <= to) { if (i >= second) ar[k] = aux[j++]; else if (j > to) ar[k] = aux[i++]; else if (aux[i] <= aux[j]) ar[k] = aux[i++]; else { ar[k] = aux[j++]; count += (second-i); } k++; } return count; } public static void main(String[] args) { Scanner in = new Scanner(System.in); int t = in.nextInt(); for(int i=0;iLarry’s Array HackerRank Solution in C#using System; using System.Linq; public class Solution { static void Main(String[] args) { var t = byte.Parse(Console.ReadLine()); for (int i = 0; i < t; i++) { Console.ReadLine(); var inp = Console.ReadLine().Split(' ').Select(int.Parse).ToList(); //var sorted = inp.OrderBy(x => x).ToList(); var sum = 0; for (int j = 0; j < inp.Count; j++) { for (int k = j+1; k < inp.Count; k++) { if (inp[k] < inp[j]) sum++; } } Console.WriteLine(sum%2==0?"YES":"NO"); } } }Attempt Larry’s Array HackerRank Challenge Link – https://www.hackerrank.com/challenges/larrys-array/ Next HackerRank Challenge Solution Link – https://exploringbits.com/almost-sorted-hackerrank-solution/ |
