HackerRank- Zig Zag Sequence problem solution in C#

 In this article, we will see the Zig Zag sequence problem solution in C#.

Problem

As per this problean m, you have element of an integer array ( ex [ 2,6,1,4,7,3,5]), Now we need to rearrange this array of elements in a zig-zag sequence, which means :

·         The first half of elements (first to the middle) are in increasing order (ex: 1, 2, 3,7).

·         The last half of elements (middle to last) are in decreasing order (ex: 7, 6, 5,4).

·         In other words: elements in increasing order < middle element > elements in decreasing order.

The output of the given array will be  

1,2,3,7,6,5,4

Given an array of n distinct integers, transform the array into a zig-zag sequence by permuting the array elements. A sequence will be called a zig-zag sequence if the first k elements in the sequence are in increasing order and the last elements are in decreasing order, where k = (n +1)/2. You need to find the lexicographically smallest zig-zag sequence of the given array.

 

Understanding problem solving

Let’s understand the algorithm by looking at input [2,6,1,4,7,3,5].

When we are going to see a Zigzag sequence (increasing order < middle > decreasing order), always remember middle element must be the largest element, so as per the given array 7 is the largest number so the zig-zag array will be

Input: 2,6,1,4,7,3,5                                            

Zig zag: _ _ _ < 7 > _ _                                       

 Now we need to find the lexicographically smallest sequence of numbers, which means we need the smallest possible values at the beginning of the array. And they should be to be in increasing order:

Input: 2,6,1,4,7,3,5                                              

Zig zag: 1, 2, 3 < 7 > _ _ _                                   

 

After this, we need the largest element at the end of the array, which means we can swap it to the middle:

Input: 2,6,1,4,7,3,5                                             

Sorted: 1, 2, 3, 4, 5, 6, 7                     

Swap largest to middle: 1, 2, 3 < 7 > 5, 6, 4

 

Finally, the last half of the elements (7, 5, 6, 4) need to be put in decreasing order (7, 6, 5, 4). The middle (7) and last element (4) were swapped and are already in the correct positions. We can reverse the remaining elements (5, 6) to put them in decreasing order (6, 5):

Input: 2,6,1,4,7,3,5                                                                                                                                    

Sorted: 1, 2, 3, 4, 5, 6, 7
Swap largest to middle: 1, 2, 3 < 7 > 5, 6, 4
Reverse sort remaining: 1, 2, 3, < 7 > 6, 5, 4
Code language: plaintext (plaintext)

And that’s the zig-zag sequence: 1, 2, 3, 7, 6,

And that’s the zig-zag sequence: 1, 2, 3, 7, 6, 5, 4. 

Here is an example of the algorithm (implemented in C#):

 public static void zigZagSequesnce()
        {
            int[] arr = new int[] { 2, 6, 1, 4, 7, 3, 5 };
            int length = arr.Length;
            int midIndex = length / 2;
            int lastIndex = length - 1;

            //Step 1 - Sort
            Array.Sort(arr);

            //Step 2 - Swap largest element into the middle
            int max = arr[lastIndex];
            arr[lastIndex] = arr[midIndex]; //7 / 2 = 3.5, 3
            arr[midIndex] = max;

            //Step 3 - Reverse remaining elements
            int leftIndex = midIndex + 1;
            int rightIndex = lastIndex - 1;

            while (leftIndex < rightIndex)
            {
                int tmp = arr[leftIndex];
                arr[leftIndex] = arr[rightIndex];
                arr[rightIndex] = tmp;

                leftIndex++;
                rightIndex--;
            }

            Console.WriteLine(string.Join(",", arr));
            Console.ReadLine();
        }

















Code language: C# (cs)

The outputs are the zig-zag sequence:

1,2,3,7,6,5,4

----------------------------------------------------------------------------------------

Author : Dotnet Office | https://www.youtube.com/TheDotNetOffice

Share this

Related Posts