Permutation game Discussions | Algorithms | HackerRank
  • + 0 comments

    C# Solution **using System; using System.Collections.Generic; using System.Linq;

    public class Solution { private static Dictionary memo = new Dictionary();

    private static bool IsIncreasing(int[] arr)
    {
        for (int i = 0; i < arr.Length - 1; i++)
        {
            if (arr[i] >= arr[i + 1])
            {
                return false;
            }
        }
        return true;
    }
    
    private static bool FindWinner(int[] arr)
    {
        string key = string.Join("|", arr);
        if (memo.ContainsKey(key))
        {
            return memo[key];
        }
    
        if (IsIncreasing(arr))
        {
            return memo[key] = true;
        }
    
        for (int idx = 0; idx < arr.Length; idx++)
        {
            var newArr = arr.Where((val, index) => index != idx).ToArray();
            if (FindWinner(newArr))
            {
                return memo[key] = false;
            }
        }
    
        return memo[key] = true;
    }
    
    public static string PermutationGame(int[] arr)
    {
        memo.Clear(); // Clear the memo dictionary for each test case
        return FindWinner(arr) ? "Bob" : "Alice";
    }
    
    public static void Main(string[] args)
    {
        int t = Convert.ToInt32(Console.ReadLine());
        while (t-- > 0)
        {
            int n = Convert.ToInt32(Console.ReadLine());
            int[] arr = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
            Console.WriteLine(PermutationGame(arr));
        }
    }
    

    }**