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.
  1. Prepare
  2. Algorithms
  3. Implementation
  4. Larry's Array
  5. Discussions

Larry's Array

Sort by

recency

|

361 Discussions

|

  • xavi_aclm
     + 0 comments

    this really just asks if you have an even permutation. you can calculate the sign in linear time by multiplying up the signs of each cycle within - the code is relatively straightforward. counting inversions may work too, although this is quadratic

  • saminazubair93
     + 0 comments
    $length = count($input);
$result = 'YES';

for ($i=0; $i < $length ; $i++) { 
	if ($input[$i] == $i+1) {
		continue;
	}
	else
	{
			while ($input[$i] !== $i+1) {
				
				$searchElement =  $i+1;
		
				$index = array_search($searchElement, $input);
				
				$diff = $index -$searchElement;

				if($diff == 0)
				{

					 if (!isset($input[$index+1])) {
			          $result = 'NO';
			           break 2; // stop the while loop
			        }

					$first = $input[$index-1]; //5
					$second = $input[$index];//2;
					$third = $input[$index+1];//6

					$input[$index] = $third;
				    $input[$index-1] =$second;
				    $input[$index+1] = $first;

				}
				else
				{

				 $first =$input[$index]; //2
 				 $second =$input[$index-1]; //5
				 $third =$input[$index-2]; //6
				
				$input[$index] = $third;
				$input[$index-1] =$first;
				$input[$index-2] = $second;

				}


			}
			
	}

}
	echo $result;``

  • just_another_dev
     + 0 comments

    hey,

    How come hidden test case 4 1 3 2 would return "YES", obvious it should be "NO" right?

  • saminsadmanshad
     + 1 comment

    Theory: (a, b, c) -> (b, c, a) is a 3-cycle permutation. That means the permutation (b, c, a) of (a, b, c) is achieved by shifting 3 consecutive numbers(cycle) which are sorted.

    Now, if a permutation can be built with even number of swaps, then its even permutation, otherwise it is an odd permutation. Our goal is to built the sorted array from the given one by 3-cycle permutation, which is an even permutation itself.

    Now, if (i, j) are two indices such that i) i < j ii) A[i] > A[j] then its called an inversion, which simply means this pair on non-consecutive numbers in an array is unsorted.

    It is important to note that every swap of two elements change the parity of inversion count. For example, for an array (4, 3, 1) , 4 > 3 ---> inversion count =1 4 > 1 ----> inversion count =2 3 > 1 ----> inversion count = 3 so, inversion count parity is odd if we swap (3, 1) --> (4, 1, 3) now the inversion count will be 2, which is even parity. Just one swap changes the parity odd to even

    Now, a 3-cycle permutation is an even permutation, which preserves the parity of inversion count since the permutation is achived by two swaps in a row. That means if we start with an array which have even number of inversion, after doing the 3-cycle permutation on it any given number of times, the array will still have an even number of inversions or vice versa

    Our goal is to make the array 0 inversion count, which is actually an even inversion count. Therefore, if the number of inversion in an array is even, then the array can be sorted by 3-cycle permutation, as the initial parity of inversion count(even) will be preserved and ended with inversion count 0(even as well)

    solution in c#:

    public static string larrysArray(List<int> A)
    {
        int inversionCount =0 ;
        for(int i = 0; i< A.Count; i++)
        {
            for(int j= i; j<A.Count; j++)
            {
                if(A[i] > A[j]) inversionCount++;
            }
        }

        return (inversionCount %2) == 0 ? "YES": "NO";
}

  • yashdeora98294
     + 0 comments

    Here is problem solution in python java c++ c and Javascript - https://programmingoneonone.com/hackerrank-larrys-array-problem-solution.html