Find Whether Each Element of One Array Occurs Same Number of Times In Second Array - O(n)

Problem:
Given two arrays find out if each element in array1 occurs same number of time in array2 :-
input = {2,3,4,2,3}
{3,2,3,2,4}
output = true

Solution 1:

Below solutions assumes that numbers are positive. If two arrays contains same numbers in any order then XOR of all elements of one array must be same as XOR of all elements of another array.


This does not work in case where XOR result of two arrays are same. As Anshu Pointed out in his comments e.g.  [36, 74] is same as [98, 12] See my other solutions in such case.

        static bool AreTheySameArrays(int[] arr1, int[] arr2)
        {
            if (arr1.Length != arr2.Length) return false;
            int xor1 = arr1[0]; int xor2 = arr2[0];
            for (int i = 1; i < arr1.Length; i++) { xor1 = xor1 ^ arr1[i]; xor2 = xor2 ^ arr2[i]; }
            return (xor1 == xor2);            
       

Solution 2:

This solution covers all the cases.  This approach uses brute force approach of keeping the count of each element in first array and reducing the same when we find the same element in second array. Finally, we iterate over this count list to find whether all the elements have count as zero. If not return false.



        static bool AreTheySameArraysUsingDictionary(int[] arr1, int[] arr2)
        {
            if (arr1.Length != arr2.Length) return false;
            Dictionary<int, int> countTable = new Dictionary<int,int>();
            for (int i = 0; i < arr1.Length; i++)
            {
                if (countTable.ContainsKey(arr1[i])) { countTable[arr1[i]]++; }
                else countTable.Add(arr1[i], 1);
            }

            for (int i = 0; i < arr2.Length; i++)
            {
                if (countTable.ContainsKey(arr2[i])) { countTable[arr2[i]]--; }
                else return false;
            }
            foreach(KeyValuePair<int,int> entry in countTable)
            {
                if (entry.Value != 0) return false;
            }
            return true;
        }


Note:
Solution is not tested regressive. If you find it not working let me know.