dev.to staff

Posted on

# Daily Challenge #213 - Are they the "same"?

Given two arrays `a` and `b` write a function comp(a, b) (compSame(a, b) in Clojure) that checks whether the two arrays have the "same" elements, with the same multiplicities. "Same" means, here, that the elements in `b` are the elements in `a` squared, regardless of the order.

Examples
Valid arrays
`a = [121, 144, 19, 161, 19, 144, 19, 11]`
`b = [121, 14641, 20736, 361, 25921, 361, 20736, 361]`
`comp(a, b)` returns true because in `b` 121 is the square of 11, 14641 is the square of 121, 20736 the square of 144, 361 the square of 19, 25921 the square of 161, and so on. It gets obvious if we write `b`'s elements in terms of squares:

`a = [121, 144, 19, 161, 19, 144, 19, 11]`
`b = [11*11, 121*121, 144*144, 19*19, 161*161, 19*19, 144*144, 19*19]`
Invalid arrays
If we change the first number to something else, `comp` may not return true anymore:

`a = [121, 144, 19, 161, 19, 144, 19, 11]`
`b = [132, 14641, 20736, 361, 25921, 361, 20736, 361]`
`comp(a,b)` returns false because in `b` 132 is not the square of any number of `a`.

`a = [121, 144, 19, 161, 19, 144, 19, 11]`
`b = [121, 14641, 20736, 36100, 25921, 361, 20736, 361]`
`comp(a,b)` returns false because in `b` 36100 is not the square of any number of `a`.

Remarks
`a` or `b` might be . a or b might be nil or null or None or nothing (except in Haskell, Elixir, C++, Rust, R, Shell, PureScript).

If `a` or `b` are nil (or null or None), the problem doesn't make sense so return false. If `a` or `b` are empty then the result is self-evident.

### Tests

a1 = [121, 144, 19, 161, 19, 144, 19, 11]
a2 = [11*11, 121*121, 144*144, 19*19, 161*161, 19*19, 144*144, 19*19]

Have fun!

This challenge comes from g964 on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

Vidit Sarkar • Edited

Python solution

``````from collections import Counter
comp = lambda a, b: a != None and b != None and Counter(map(lambda x: x*x,a))==Counter(b)

print(comp([121, 144, 19, 161, 19, 144, 19, 11], [121, 14641, 20736, 361, 25921, 361, 20736, 361])) # True
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])) # True
print(comp([121, 144, 19, 161, 19, 144, 19, 11], [132, 14641, 20736, 361, 25921, 361, 20736, 361])) # False
print(comp([121, 144, 19, 161, 19, 144, 19, 11], [121, 14641, 20736, 36100, 25921, 361, 20736, 361])) # False
print(comp([], [])) # True
print(comp([1,2,3,4],None)) # False
print(comp(None, None)) # False
``````

Valts Liepiņš • Edited

``````import Data.List (sort)

comp :: [Int] -> [Int] -> Bool
comp a b
| length a == length b = all same \$ zip (fmap sq . sort \$ a) (sort b)
| otherwise            = False
where sq x = x*x
same x = fst x == snd x
``````

Edit:
I wanted to implement the O(a + b) solution in Haskell as well:

``````import qualified Data.IntMap.Strict as Map
type Freq = Map.IntMap Int

comp :: [Int] -> [Int] -> Bool
comp as bs
| length as == length bs = freq (fmap (^2) as) == freq bs
| otherwise              = False
where
freq = foldr inc Map.empty
inc k = Map.insertWith (+) k 1
``````

Craig McIlwrath

Why use `all same`? Can't you directly test `map (^2) (sort a) == sort b`?

Valts Liepiņš

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.

Craig McIlwrath

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.

Kermit Alexander II • Edited

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

def calc_frequency(l):
freqs = {}
for num in l:
freqs[num] = freqs.get(num, 0) + 1
return freqs

def comp(a, b):
if a is None or b is None:
# early exit on null arrays
return False
b_freqs = calc_frequency(b)
for num in a:
square = num ** 2
if square not in b_freqs:
# early exit if the square of some value in a simply isn't in b
return False
b_freqs[square] -= 1
for freq in b_freqs.values():
if freq != 0:
# could be < 0 if a has more occurrences, or > 0 if b has more occurrences
return False
return True

if __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))
``````

Sabin Pandelovitch • Edited

JS solution

``````const comp = (a, b) => {
if (
a === null ||
b === null ||
a.length === 0 ||
b.length === 0 ||
a.length !== b.length
) {
return false;
}

let status = true;
let i = 0;
while (status && i < a.length) {
status = b.indexOf(Math.pow(a[i],2)) > -1
i++;
}

return status;
};
``````

*fixed

kesprit

My Swift solution :

``````func comp(a: [Int], b: [Int]) -> Bool {
guard !a.isEmpty, !b.isEmpty, a.count == b.count else { return false }

return a.reduce(into: true) {
\$0 = b.contains(\$1 * \$1)
}
}
``````

K.V.Harish • Edited

My solution in JavaScript

``````const comp = (arr1, arr2) => {
if(Array.isArray(arr1) && arr1.length && Array.isArray(arr2) && arr2.length) {
return arr1.sort((a, b) => a - b).toString() === arr2.sort((a, b) => a - b).map(c => Math.sqrt(c)).toString()
}
return false;
};

// Valid arrays
console.log(comp([121, 144, 19, 161, 19, 144, 19, 11], [121, 14641, 20736, 361, 25921, 361, 20736, 361])); // true
console.log(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])); // true
// Invalid arrays
console.log(comp([121, 144, 19, 161, 19, 144, 19, 11], [132, 14641, 20736, 361, 25921, 361, 20736, 361])); // false
console.log(comp([121, 144, 19, 161, 19, 144, 19, 11], [121, 14641, 20736, 36100, 25921, 361, 20736, 361])); // false
``````

Vidit Sarkar • Edited

C++ solution

``````bool comp(vector<int> a, vector<int> b){
// if both of them have no element then return true
if(a.size() == 0 || b.size() == 0)
return true;

// if they have different size then return false
if(a.size() != b.size())
return false;

int size = a.size(); // or b.size() as both of them have same size
unordered_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(int i=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 false
for(auto it : squareCount){
if(it.second != 0)
return false;
}
return true;
}
``````

Nilbert

Ruby

``````def comp(array1, array2)
return false if array1.nil?  || array2.nil?
#method 1 compare dic
array1.map{|x| x*x}.group_by(&:itself) == array2.group_by(&:itself)
#method 2 compare sorted array
array1.sort.map {|x| x*x} == array2.sort
end
``````

Ksenia

Python:

``````def comp(a: list, b: list) -> bool:
flag = False
if a == None or b == None:
return flag
elif len(a) == 0 and len(b) == 0:
return True
for val_a in a:
flag = False
for ind_b, val_b in enumerate(b):
if val_a*val_a == val_b and flag == False:
b.pop(ind_b)
flag = True
if len(b) == 0:
return flag
else:
return False
``````

Php solution

`````` function comp(\$a1, \$a2)
{
if ( is_null(\$a1) || is_null(\$a2) )
return false;

\$t = array_map(function(\$v) {
return \$v * \$v;
}, \$a1);

sort(\$a2);
sort(\$t);
return \$a2 == \$t;
}
``````