using System;

using System.Collections.Generic;

​

public class Solution

{

    public static void Main(string[] args)

    {

        int[] cards = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

        cards = Shuffle(cards);

        foreach (int i in cards)

        {

            Console.Write(i + " ");

        }

​

        Console.WriteLine();

    }

​

    /*

 The shuffle card function does 2 things:

 1. Shuffle the value in each position of input array, so after it processed the input array, 

    the out array shall have different value in each index comparing the input array

 2. The shuffle algorithm shall be unpredictable so one can not guess the output with input array.

    //10 4 5 3 8 1 6 9 7 2

    //2 6 9 8 1 5 10 3 7 4

 */

    // fisher yates algorithm

    public static int[] Shuffle(int[] arr) //O(n) Time ; Space O(1)

    {

        Random rand = new Random();

        for(int i = arr.Length -1; i > 0; i--){

            int randomIndex = rand.Next(0, i+1);

            int temp = arr[randomIndex];

            arr[randomIndex] = arr[i];

            arr[i]= temp;

        }

        return arr;

    }

    public static int[] Shuffle1(int[] arr)

    {

        HashSet<int> hashSet = new HashSet<int>();

        int counter = 0;

        Random rand = new Random();

        int i=0;

        while(i< arr.Length)

        {

            int randomIndex = rand.Next(0, arr.Length -1);

            if(hashSet.Contains(randomIndex) == false){

                counter++;

                int temp= arr[randomIndex];

                arr[randomIndex] = arr[i];

                arr[i]=temp;

                i++;

            }

        }

        Console.WriteLine("Ran for :" + counter);

        return arr;

    }

}