1
$\begingroup$

Problem description

We are given two sorted arrays of even numbers: A and B. Values of A are generally supposed to be smaller than values of B. So we are asked to find a value X where X is an odd number to predict which set an element belongs to. If an element is smaller than X, it will be assigned to A,and if it is bigger - to B. The value should be optimal, meaning the number of improperly matched values should be minimal. For example, if A = [2,4,6] and B = [6, 10, 12]. Separating value 3 would cause 2 mismatched values 4 and 6. Optimal would be 5 or 7, both causing one improper matched element. The algorithm is supposed to return an optimal separating value (only one of there are many) and the number of mismatched items.

My ideas

At first I thought about using Binary Search for each element of A to find a number of elements of B smaller than it. Then repeat for B.

A better idea would be to generate candidates for such separating numbers. For example, if we only have values 10, 50, 100 we don't have to check all odd numbers, we can just check 9, 11, 51, 101. We could then calculate prefix sums, indicating how many numbers from A are bigger than the checked value and how many elements from B are smart than that value. The sum of the two sums for a number would be the total number of errors. The only thing left is to find the value with minimal errors.

Is this approach even near optimal, maybe we can find a better way. Also, calculating such prefix sums can be tricky because if we want not to care about the range of numbers we would have to find a way to skip some numbers and that makes our iteration harder, although possible.

What are your ideas? Some pseudocode or code in Python is very welcome.

$\endgroup$
1
$\begingroup$

Initialize an array of pairs $T[i] = (x, c)$ containing all elements of $A$ and $B$. Let $x$ be the elements themselves, and $c = 0$ if the element came from $A$ and $c = 1$ if the element came from $B$. Then sort $T$ based on the $x$ values in ascending order.

Then the number of mistakes you'd get if you choose a value between $T[i]\text{.}x$ and $T[i+1]\text{.}x$ is:

$$\sum_{j=0}^i T[j]\text{.}c + \sum_{j=i+1}^n\left(1 - T[j]\text{.}c\right) = $$ $$(n - i) +\sum_{j=0}^i T[j]\text{.}c - \sum_{j=i+1}^nT[j]\text{.}c = $$ $$(n - i) +2\sum_{j=0}^i T[j]\text{.}c - \sum_{j=0}^nT[j]\text{.}c = $$ $$- i +2\sum_{j=0}^i T[j]\text{.}c - C$$

where $C$ is just a constant, which doesn't matter if you wish to minimize the quantity. So to find the optimal value:

S = 0
best = inf
best_i = 1
for 1 <= i <= n:
    S += 2*T[i].c
    if S - i < best:
        best = S - i
        best_i = i
$\endgroup$
2
  • $\begingroup$ Much simpler and cleaner, although not necessarily faster. Your solution is O(m) where m is the data spread. Mine is always O(n). Thank you anyway. $\endgroup$ – Kangaroo976 Jan 8 at 12:09
  • $\begingroup$ @Kangaroo976 No? Nothing relies on the data spread. Also my solution is $O(n \log n)$ because of the sorting operation. Unless $A$ and $B$ come pre-sorted in which case you can use an $O(n)$ merge, but you never mentioned that they were sorted. $\endgroup$ – orlp Jan 8 at 12:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.