a%b=abs$a-b
x@(a:b)#y@(c:d)|e:_<-d,a%c>a%e=x#d|1>0=a%c+b#y
_#_=0
Try it online!
Explanation
First we define (%)
to be the absolute difference between two numbers. Then we define (#)
to be the interesting function. In the first line we match when both lists are non-empty:
x@(a:b)#(c:d:e)
On our first case from here we bind d
to e:_
with e:_<-d
. This ensures that d
is non-empty and sets it's first element to e
.
Then if the second element of \$Y\$ (e
) is closer than the first (c
) to the first element of \$X\$ (a
), we return x#d
removing the first element of \$Y\$ and calling again with the same \$X\$.
If we match the pattern but don't pass the condition we do:
a%c+b#y
Which, removes the first item of \$X\$ and adds the absolute difference of it from the first element of \$X\$ to the remaining result.
Lastly if we don't match the pattern we return \$0\$. Not matching the pattern means that \$X\$ must be empty because \$Y\$ cannot be empty.
This algorithm has order notation \$O(|X|+|Y|)\$.
Here's how I would do it in \$O(\left|X\right|\times\left|Y\right|)\$ time:
x#y=sum[minimum$abs.(z-)<$>y|z<-x]
Try it online!
Can we use lists or streams instead of arrays? – Post Rock Garf Hunter – 2018-07-01T17:59:11.880
@CatWizard Yes you can! – Anush – 2018-07-01T17:59:33.497
1How is
1 + 2 + 3
derived fromX = (1,2,3)
andY = (0,8)
? – guest271314 – 2018-07-01T20:47:26.2071@guest271314 the closest number two each of
1
,2
, and3
inY
is0
. Thus the differences are1-0
,2-0
,3-0
. – dylnan – 2018-07-01T21:03:35.427@user202729 I clarified this in the question. In general, it is standard to assume you can add two O(\log n) bit integers in constant time unless you specify otherwise. – Anush – 2018-07-02T06:24:35.167
I'm not quite sure this is possible. Taking 2 arrays of numbers and finding the least differences will always take O(n) time, where n is the product of the length of the arrays. – FreezePhoenix – 2018-07-02T13:21:40.570
1@FreezePhoenix since both lists are sorted you can do it in O(n+m), because you iterate over list $X$, visiting each element once, and as long as you keep track of the element $Y_j$ closest to $X_i$, you can check against $Y_j$ and $Y_{j+1}$ since one of those is closest to $X_{i+1}$ – Giuseppe – 2018-07-02T13:51:49.897
Are the arrays always non-negative integers? – Giuseppe – 2018-07-02T13:53:59.487
@Giuseppe No, sorry. – Anush – 2018-07-02T19:41:06.413