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!
Top comments (15)
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
b
must be accounted for, as we see with the test case with36100
as a value. Additionally, we can't use a set for this problem since values may show up in eithera
orb
multiple 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
My Swift solution :
My solution in JavaScript
C++ solution
Ruby
Python:
Php solution