ORIGINAL CODING QUESTION

Twice the merged median

Return TWICE the median of two nondecreasing arrays, so the output remains an integer. For even length add the two central values; for odd length double the central value.

Open practice workspace

Original exercise · hard. Editorial role relevance does not imply a company has asked this question.

Input and output

n, n sorted values, m, m sorted values.

Constraints

1 ≤ n,m ≤ 100; -100 ≤ value ≤ 100.

Example 1

Input

2 1 3 1 2

Output

The median is 2, so print 4.

Example 2

Input

2 1 2 2 3 4

Output

The median is 2.5, so print 5.

Explain your approach

Explain your time and auxiliary space complexity. Which input makes your algorithm work hardest?

Private grading inputs, expected outputs and canonical reference implementations are withheld. Authored expected outputs were cross-checked with independent reference oracles; compiler/runtime behavior still needs a verified execution provider.

Hint 1

The median divides the ordered values into balanced halves.

Hint 2

Choose cuts with all left values at most all right values.

Hint 3

Twice the median avoids floating-point formatting.

Practice this question

Save your work privately, explain decisions and return to your revision queue.

Open practice workspace Browse the question library →