It's not really deep comparison, it uses the Eq class (==) function. For the primitives, it's by value. For ADTs that derive Eq, it checks equality for all of the values in the ADT, which functions that same as deep comparison.
The main point to keep in mind with this one is that all values in b must be accounted for, as we see with the test case with 36100 as a value. Additionally, we can't use a set for this problem since values may show up in either a or b multiple times, so that's out. So instead, we can calculate the frequency of occurrences of values instead, which leads to this O(a + b) solution:
#!/usr/bin/env python3
defcalc_frequency(l):freqs={}fornuminl:freqs[num]=freqs.get(num,0)+1returnfreqsdefcomp(a,b):ifaisNoneorbisNone:# early exit on null arrays
returnFalseb_freqs=calc_frequency(b)fornumina:square=num**2ifsquarenotinb_freqs:# early exit if the square of some value in a simply isn't in b
returnFalseb_freqs[square]-=1forfreqinb_freqs.values():iffreq!=0:# could be < 0 if a has more occurrences, or > 0 if b has more occurrences
returnFalsereturnTrueif__name__=="__main__":print(comp([121,144,19,161,19,144,19,11],[121,14641,20736,361,25921,361,20736,361]))print(comp([121,144,19,161,19,144,19,11],[11*11,121*121,144*144,19*19,161*161,19*19,144*144,19*19]))print(comp([121,144,19,161,19,144,19,11],[132,14641,20736,361,25921,361,20736,361]))print(comp([121,144,19,161,19,144,19,11],[121,14641,20736,36100,25921,361,20736,361]))print(comp([],[]))print(comp([1,2,3],None))
boolcomp(vector<int>a,vector<int>b){// if both of them have no element then return trueif(a.size()==0||b.size()==0)returntrue;// if they have different size then return falseif(a.size()!=b.size())returnfalse;intsize=a.size();// or b.size() as both of them have same sizeunordered_map<int,int>squareCount;// squares a number of a, increment squareCount[squareNumber_a] by 1 i.e. squareCount[squareNumber_a]++// decrement sqareCount[squareNumber_b] by 1 i.e. squareCount[squareNumber_b]--for(inti=0;i<size;i++){squareCount[a[i]*a[i]]++;squareCount[b[i]]--;}// if they are "same" then all the values of corresponding// keys of sqaureCount will be zero// if any one of them is not zero then return falsefor(autoit:squareCount){if(it.second!=0)returnfalse;}returntrue;}
Python solution
Solution in Haskell:
Edit:
I wanted to implement the O(a + b) solution in Haskell as well:
Why use
all same? Can't you directly testmap (^2) (sort a) == sort b?Wasn't aware that Haskell's equality operator did deep comparision, but that makes sense. Thanks!
I'd probably rewrite this with the O(a + b) algorithm from the other solution.
It's not really deep comparison, it uses the Eq class (==) function. For the primitives, it's by value. For ADTs that derive Eq, it checks equality for all of the values in the ADT, which functions that same as deep comparison.
The main point to keep in mind with this one is that all values in
bmust be accounted for, as we see with the test case with36100as a value. Additionally, we can't use a set for this problem since values may show up in eitheraorbmultiple times, so that's out. So instead, we can calculate the frequency of occurrences of values instead, which leads to thisO(a + b)solution:JS solution
*fixed
C++ solution
Ruby
My Swift solution :
My solution in JavaScript
Python:
Php solution
Anyone have PHP Solution???