Given two slices of sorted arrays, find the median. Repeat for many such slices, return the median of the results.
Sign up for our newsletter:
Information about upcoming challenges, solutions and lessons directly in your inbox.
Social:
The median of a sequence of numbers X[0], X[1], ..., X[N] is the middle element in terms of their values. More formally, the median of X[0], X[1], ..., X[N] is an element X[I] of the sequence, such that at most half of the elements are larger than X[I] and at most half of the elements are smaller than X[I]. For example, the median of the following sequence:
X[0] = 7 X[1] = 2 X[2] = 5 X[3] = 2 X[4] = 8is 5; the median of the following sequence:
X[0] = 2 X[1] = 2 X[2] = 5 X[3] = 2is 2; and the following sequence:
X[0] = 1 X[1] = 5 X[2] = 7 X[3] = 4 X[4] = 2 X[5] = 8has two medians: 4 and 5.
Note that sequences of odd length have only one median, which is equal to X[N/2] after sorting X. In this problem we consider medians of sequences of odd length only.
Write a function:
int solution(int A[], int N, int B[], int M, int P[], int Q[], int R[], int S[], int K);
that, given:
- two non-empty arrays, A (consisting of N integers) and B (consisting of M integers), both sorted in ascending order
- two arrays P and Q, each consisting of K indices of array A, such that 0 ≤ P[I] ≤ Q[I] < N for 0 ≤ I < K
- two arrays R and S, each consisting of K indices of array B, such that 0 ≤ R[I] ≤ S[I] < M for 0 ≤ I < K
computes medians of K sequences of the form:
A[P[I]], A[P[I]+1], ..., A[Q[I]-1], A[Q[I]], B[R[I]], B[R[I]+1], ..., B[S[I]-1], B[S[I]]for 0 ≤ I < K, and returns the median of all such medians.
For example, given the following arrays:
A[0] = -2 A[1] = 4 A[2] = 10 A[3] = 13 B[0] = 5 B[1] = 6 B[2] = 8 B[3] = 12 B[4] = 13 P[0] = 2 P[1] = 1 P[2] = 0 Q[0] = 3 Q[1] = 2 Q[2] = 3 R[0] = 0 R[1] = 0 R[2] = 1 S[0] = 4 S[1] = 0 S[2] = 3the function should return 8, since:
- the median of [10, 13, 5, 6, 8, 12, 13] equals 10,
- the median of [4, 10, 5] equals 5,
- the median of [−2, 4, 10, 13, 6, 8, 12] equals 8, and
- the median of [10, 5, 8] equals 8.
Write an efficient algorithm for the following assumptions:
- N and M are integers within the range [1..100,000];
- K is an integer within the range [1..10,000];
- each element of arrays A and B is an integer within the range [−1,000,000,000..1,000,000,000];
- array A is sorted in non-decreasing order;
- array B is sorted in non-decreasing order;
- each element of arrays P and Q is an integer within the range [0..N-1];
- each element of arrays R and S is an integer within the range [0..M-1];
- P[i] ≤ Q[i] and R[i] ≤ S[i] for 0 ≤ i < K;
- K is odd and so is Q[i]−P[i]+R[i]−S[i] for 0 ≤ i < K.
The median of a sequence of numbers X[0], X[1], ..., X[N] is the middle element in terms of their values. More formally, the median of X[0], X[1], ..., X[N] is an element X[I] of the sequence, such that at most half of the elements are larger than X[I] and at most half of the elements are smaller than X[I]. For example, the median of the following sequence:
X[0] = 7 X[1] = 2 X[2] = 5 X[3] = 2 X[4] = 8is 5; the median of the following sequence:
X[0] = 2 X[1] = 2 X[2] = 5 X[3] = 2is 2; and the following sequence:
X[0] = 1 X[1] = 5 X[2] = 7 X[3] = 4 X[4] = 2 X[5] = 8has two medians: 4 and 5.
Note that sequences of odd length have only one median, which is equal to X[N/2] after sorting X. In this problem we consider medians of sequences of odd length only.
Write a function:
int solution(vector<int> &A, vector<int> &B, vector<int> &P, vector<int> &Q, vector<int> &R, vector<int> &S);
that, given:
- two non-empty arrays, A (consisting of N integers) and B (consisting of M integers), both sorted in ascending order
- two arrays P and Q, each consisting of K indices of array A, such that 0 ≤ P[I] ≤ Q[I] < N for 0 ≤ I < K
- two arrays R and S, each consisting of K indices of array B, such that 0 ≤ R[I] ≤ S[I] < M for 0 ≤ I < K
computes medians of K sequences of the form:
A[P[I]], A[P[I]+1], ..., A[Q[I]-1], A[Q[I]], B[R[I]], B[R[I]+1], ..., B[S[I]-1], B[S[I]]for 0 ≤ I < K, and returns the median of all such medians.
For example, given the following arrays:
A[0] = -2 A[1] = 4 A[2] = 10 A[3] = 13 B[0] = 5 B[1] = 6 B[2] = 8 B[3] = 12 B[4] = 13 P[0] = 2 P[1] = 1 P[2] = 0 Q[0] = 3 Q[1] = 2 Q[2] = 3 R[0] = 0 R[1] = 0 R[2] = 1 S[0] = 4 S[1] = 0 S[2] = 3the function should return 8, since:
- the median of [10, 13, 5, 6, 8, 12, 13] equals 10,
- the median of [4, 10, 5] equals 5,
- the median of [−2, 4, 10, 13, 6, 8, 12] equals 8, and
- the median of [10, 5, 8] equals 8.
Write an efficient algorithm for the following assumptions:
- N and M are integers within the range [1..100,000];
- K is an integer within the range [1..10,000];
- each element of arrays A and B is an integer within the range [−1,000,000,000..1,000,000,000];
- array A is sorted in non-decreasing order;
- array B is sorted in non-decreasing order;
- each element of arrays P and Q is an integer within the range [0..N-1];
- each element of arrays R and S is an integer within the range [0..M-1];
- P[i] ≤ Q[i] and R[i] ≤ S[i] for 0 ≤ i < K;
- K is odd and so is Q[i]−P[i]+R[i]−S[i] for 0 ≤ i < K.
The median of a sequence of numbers X[0], X[1], ..., X[N] is the middle element in terms of their values. More formally, the median of X[0], X[1], ..., X[N] is an element X[I] of the sequence, such that at most half of the elements are larger than X[I] and at most half of the elements are smaller than X[I]. For example, the median of the following sequence:
X[0] = 7 X[1] = 2 X[2] = 5 X[3] = 2 X[4] = 8is 5; the median of the following sequence:
X[0] = 2 X[1] = 2 X[2] = 5 X[3] = 2is 2; and the following sequence:
X[0] = 1 X[1] = 5 X[2] = 7 X[3] = 4 X[4] = 2 X[5] = 8has two medians: 4 and 5.
Note that sequences of odd length have only one median, which is equal to X[N/2] after sorting X. In this problem we consider medians of sequences of odd length only.
Write a function:
int solution(vector<int> &A, vector<int> &B, vector<int> &P, vector<int> &Q, vector<int> &R, vector<int> &S);
that, given:
- two non-empty arrays, A (consisting of N integers) and B (consisting of M integers), both sorted in ascending order
- two arrays P and Q, each consisting of K indices of array A, such that 0 ≤ P[I] ≤ Q[I] < N for 0 ≤ I < K
- two arrays R and S, each consisting of K indices of array B, such that 0 ≤ R[I] ≤ S[I] < M for 0 ≤ I < K
computes medians of K sequences of the form:
A[P[I]], A[P[I]+1], ..., A[Q[I]-1], A[Q[I]], B[R[I]], B[R[I]+1], ..., B[S[I]-1], B[S[I]]for 0 ≤ I < K, and returns the median of all such medians.
For example, given the following arrays:
A[0] = -2 A[1] = 4 A[2] = 10 A[3] = 13 B[0] = 5 B[1] = 6 B[2] = 8 B[3] = 12 B[4] = 13 P[0] = 2 P[1] = 1 P[2] = 0 Q[0] = 3 Q[1] = 2 Q[2] = 3 R[0] = 0 R[1] = 0 R[2] = 1 S[0] = 4 S[1] = 0 S[2] = 3the function should return 8, since:
- the median of [10, 13, 5, 6, 8, 12, 13] equals 10,
- the median of [4, 10, 5] equals 5,
- the median of [−2, 4, 10, 13, 6, 8, 12] equals 8, and
- the median of [10, 5, 8] equals 8.
Write an efficient algorithm for the following assumptions:
- N and M are integers within the range [1..100,000];
- K is an integer within the range [1..10,000];
- each element of arrays A and B is an integer within the range [−1,000,000,000..1,000,000,000];
- array A is sorted in non-decreasing order;
- array B is sorted in non-decreasing order;
- each element of arrays P and Q is an integer within the range [0..N-1];
- each element of arrays R and S is an integer within the range [0..M-1];
- P[i] ≤ Q[i] and R[i] ≤ S[i] for 0 ≤ i < K;
- K is odd and so is Q[i]−P[i]+R[i]−S[i] for 0 ≤ i < K.
The median of a sequence of numbers X[0], X[1], ..., X[N] is the middle element in terms of their values. More formally, the median of X[0], X[1], ..., X[N] is an element X[I] of the sequence, such that at most half of the elements are larger than X[I] and at most half of the elements are smaller than X[I]. For example, the median of the following sequence:
X[0] = 7 X[1] = 2 X[2] = 5 X[3] = 2 X[4] = 8is 5; the median of the following sequence:
X[0] = 2 X[1] = 2 X[2] = 5 X[3] = 2is 2; and the following sequence:
X[0] = 1 X[1] = 5 X[2] = 7 X[3] = 4 X[4] = 2 X[5] = 8has two medians: 4 and 5.
Note that sequences of odd length have only one median, which is equal to X[N/2] after sorting X. In this problem we consider medians of sequences of odd length only.
Write a function:
class Solution { public int solution(int[] A, int[] B, int[] P, int[] Q, int[] R, int[] S); }
that, given:
- two non-empty arrays, A (consisting of N integers) and B (consisting of M integers), both sorted in ascending order
- two arrays P and Q, each consisting of K indices of array A, such that 0 ≤ P[I] ≤ Q[I] < N for 0 ≤ I < K
- two arrays R and S, each consisting of K indices of array B, such that 0 ≤ R[I] ≤ S[I] < M for 0 ≤ I < K
computes medians of K sequences of the form:
A[P[I]], A[P[I]+1], ..., A[Q[I]-1], A[Q[I]], B[R[I]], B[R[I]+1], ..., B[S[I]-1], B[S[I]]for 0 ≤ I < K, and returns the median of all such medians.
For example, given the following arrays:
A[0] = -2 A[1] = 4 A[2] = 10 A[3] = 13 B[0] = 5 B[1] = 6 B[2] = 8 B[3] = 12 B[4] = 13 P[0] = 2 P[1] = 1 P[2] = 0 Q[0] = 3 Q[1] = 2 Q[2] = 3 R[0] = 0 R[1] = 0 R[2] = 1 S[0] = 4 S[1] = 0 S[2] = 3the function should return 8, since:
- the median of [10, 13, 5, 6, 8, 12, 13] equals 10,
- the median of [4, 10, 5] equals 5,
- the median of [−2, 4, 10, 13, 6, 8, 12] equals 8, and
- the median of [10, 5, 8] equals 8.
Write an efficient algorithm for the following assumptions:
- N and M are integers within the range [1..100,000];
- K is an integer within the range [1..10,000];
- each element of arrays A and B is an integer within the range [−1,000,000,000..1,000,000,000];
- array A is sorted in non-decreasing order;
- array B is sorted in non-decreasing order;
- each element of arrays P and Q is an integer within the range [0..N-1];
- each element of arrays R and S is an integer within the range [0..M-1];
- P[i] ≤ Q[i] and R[i] ≤ S[i] for 0 ≤ i < K;
- K is odd and so is Q[i]−P[i]+R[i]−S[i] for 0 ≤ i < K.
The median of a sequence of numbers X[0], X[1], ..., X[N] is the middle element in terms of their values. More formally, the median of X[0], X[1], ..., X[N] is an element X[I] of the sequence, such that at most half of the elements are larger than X[I] and at most half of the elements are smaller than X[I]. For example, the median of the following sequence:
X[0] = 7 X[1] = 2 X[2] = 5 X[3] = 2 X[4] = 8is 5; the median of the following sequence:
X[0] = 2 X[1] = 2 X[2] = 5 X[3] = 2is 2; and the following sequence:
X[0] = 1 X[1] = 5 X[2] = 7 X[3] = 4 X[4] = 2 X[5] = 8has two medians: 4 and 5.
Note that sequences of odd length have only one median, which is equal to X[N/2] after sorting X. In this problem we consider medians of sequences of odd length only.
Write a function:
int solution(List<int> A, List<int> B, List<int> P, List<int> Q, List<int> R, List<int> S);
that, given:
- two non-empty arrays, A (consisting of N integers) and B (consisting of M integers), both sorted in ascending order
- two arrays P and Q, each consisting of K indices of array A, such that 0 ≤ P[I] ≤ Q[I] < N for 0 ≤ I < K
- two arrays R and S, each consisting of K indices of array B, such that 0 ≤ R[I] ≤ S[I] < M for 0 ≤ I < K
computes medians of K sequences of the form:
A[P[I]], A[P[I]+1], ..., A[Q[I]-1], A[Q[I]], B[R[I]], B[R[I]+1], ..., B[S[I]-1], B[S[I]]for 0 ≤ I < K, and returns the median of all such medians.
For example, given the following arrays:
A[0] = -2 A[1] = 4 A[2] = 10 A[3] = 13 B[0] = 5 B[1] = 6 B[2] = 8 B[3] = 12 B[4] = 13 P[0] = 2 P[1] = 1 P[2] = 0 Q[0] = 3 Q[1] = 2 Q[2] = 3 R[0] = 0 R[1] = 0 R[2] = 1 S[0] = 4 S[1] = 0 S[2] = 3the function should return 8, since:
- the median of [10, 13, 5, 6, 8, 12, 13] equals 10,
- the median of [4, 10, 5] equals 5,
- the median of [−2, 4, 10, 13, 6, 8, 12] equals 8, and
- the median of [10, 5, 8] equals 8.
Write an efficient algorithm for the following assumptions:
- N and M are integers within the range [1..100,000];
- K is an integer within the range [1..10,000];
- each element of arrays A and B is an integer within the range [−1,000,000,000..1,000,000,000];
- array A is sorted in non-decreasing order;
- array B is sorted in non-decreasing order;
- each element of arrays P and Q is an integer within the range [0..N-1];
- each element of arrays R and S is an integer within the range [0..M-1];
- P[i] ≤ Q[i] and R[i] ≤ S[i] for 0 ≤ i < K;
- K is odd and so is Q[i]−P[i]+R[i]−S[i] for 0 ≤ i < K.
The median of a sequence of numbers X[0], X[1], ..., X[N] is the middle element in terms of their values. More formally, the median of X[0], X[1], ..., X[N] is an element X[I] of the sequence, such that at most half of the elements are larger than X[I] and at most half of the elements are smaller than X[I]. For example, the median of the following sequence:
X[0] = 7 X[1] = 2 X[2] = 5 X[3] = 2 X[4] = 8is 5; the median of the following sequence:
X[0] = 2 X[1] = 2 X[2] = 5 X[3] = 2is 2; and the following sequence:
X[0] = 1 X[1] = 5 X[2] = 7 X[3] = 4 X[4] = 2 X[5] = 8has two medians: 4 and 5.
Note that sequences of odd length have only one median, which is equal to X[N/2] after sorting X. In this problem we consider medians of sequences of odd length only.
Write a function:
func Solution(A []int, B []int, P []int, Q []int, R []int, S []int) int
that, given:
- two non-empty arrays, A (consisting of N integers) and B (consisting of M integers), both sorted in ascending order
- two arrays P and Q, each consisting of K indices of array A, such that 0 ≤ P[I] ≤ Q[I] < N for 0 ≤ I < K
- two arrays R and S, each consisting of K indices of array B, such that 0 ≤ R[I] ≤ S[I] < M for 0 ≤ I < K
computes medians of K sequences of the form:
A[P[I]], A[P[I]+1], ..., A[Q[I]-1], A[Q[I]], B[R[I]], B[R[I]+1], ..., B[S[I]-1], B[S[I]]for 0 ≤ I < K, and returns the median of all such medians.
For example, given the following arrays:
A[0] = -2 A[1] = 4 A[2] = 10 A[3] = 13 B[0] = 5 B[1] = 6 B[2] = 8 B[3] = 12 B[4] = 13 P[0] = 2 P[1] = 1 P[2] = 0 Q[0] = 3 Q[1] = 2 Q[2] = 3 R[0] = 0 R[1] = 0 R[2] = 1 S[0] = 4 S[1] = 0 S[2] = 3the function should return 8, since:
- the median of [10, 13, 5, 6, 8, 12, 13] equals 10,
- the median of [4, 10, 5] equals 5,
- the median of [−2, 4, 10, 13, 6, 8, 12] equals 8, and
- the median of [10, 5, 8] equals 8.
Write an efficient algorithm for the following assumptions:
- N and M are integers within the range [1..100,000];
- K is an integer within the range [1..10,000];
- each element of arrays A and B is an integer within the range [−1,000,000,000..1,000,000,000];
- array A is sorted in non-decreasing order;
- array B is sorted in non-decreasing order;
- each element of arrays P and Q is an integer within the range [0..N-1];
- each element of arrays R and S is an integer within the range [0..M-1];
- P[i] ≤ Q[i] and R[i] ≤ S[i] for 0 ≤ i < K;
- K is odd and so is Q[i]−P[i]+R[i]−S[i] for 0 ≤ i < K.
The median of a sequence of numbers X[0], X[1], ..., X[N] is the middle element in terms of their values. More formally, the median of X[0], X[1], ..., X[N] is an element X[I] of the sequence, such that at most half of the elements are larger than X[I] and at most half of the elements are smaller than X[I]. For example, the median of the following sequence:
X[0] = 7 X[1] = 2 X[2] = 5 X[3] = 2 X[4] = 8is 5; the median of the following sequence:
X[0] = 2 X[1] = 2 X[2] = 5 X[3] = 2is 2; and the following sequence:
X[0] = 1 X[1] = 5 X[2] = 7 X[3] = 4 X[4] = 2 X[5] = 8has two medians: 4 and 5.
Note that sequences of odd length have only one median, which is equal to X[N/2] after sorting X. In this problem we consider medians of sequences of odd length only.
Write a function:
class Solution { public int solution(int[] A, int[] B, int[] P, int[] Q, int[] R, int[] S); }
that, given:
- two non-empty arrays, A (consisting of N integers) and B (consisting of M integers), both sorted in ascending order
- two arrays P and Q, each consisting of K indices of array A, such that 0 ≤ P[I] ≤ Q[I] < N for 0 ≤ I < K
- two arrays R and S, each consisting of K indices of array B, such that 0 ≤ R[I] ≤ S[I] < M for 0 ≤ I < K
computes medians of K sequences of the form:
A[P[I]], A[P[I]+1], ..., A[Q[I]-1], A[Q[I]], B[R[I]], B[R[I]+1], ..., B[S[I]-1], B[S[I]]for 0 ≤ I < K, and returns the median of all such medians.
For example, given the following arrays:
A[0] = -2 A[1] = 4 A[2] = 10 A[3] = 13 B[0] = 5 B[1] = 6 B[2] = 8 B[3] = 12 B[4] = 13 P[0] = 2 P[1] = 1 P[2] = 0 Q[0] = 3 Q[1] = 2 Q[2] = 3 R[0] = 0 R[1] = 0 R[2] = 1 S[0] = 4 S[1] = 0 S[2] = 3the function should return 8, since:
- the median of [10, 13, 5, 6, 8, 12, 13] equals 10,
- the median of [4, 10, 5] equals 5,
- the median of [−2, 4, 10, 13, 6, 8, 12] equals 8, and
- the median of [10, 5, 8] equals 8.
Write an efficient algorithm for the following assumptions:
- N and M are integers within the range [1..100,000];
- K is an integer within the range [1..10,000];
- each element of arrays A and B is an integer within the range [−1,000,000,000..1,000,000,000];
- array A is sorted in non-decreasing order;
- array B is sorted in non-decreasing order;
- each element of arrays P and Q is an integer within the range [0..N-1];
- each element of arrays R and S is an integer within the range [0..M-1];
- P[i] ≤ Q[i] and R[i] ≤ S[i] for 0 ≤ i < K;
- K is odd and so is Q[i]−P[i]+R[i]−S[i] for 0 ≤ i < K.
The median of a sequence of numbers X[0], X[1], ..., X[N] is the middle element in terms of their values. More formally, the median of X[0], X[1], ..., X[N] is an element X[I] of the sequence, such that at most half of the elements are larger than X[I] and at most half of the elements are smaller than X[I]. For example, the median of the following sequence:
X[0] = 7 X[1] = 2 X[2] = 5 X[3] = 2 X[4] = 8is 5; the median of the following sequence:
X[0] = 2 X[1] = 2 X[2] = 5 X[3] = 2is 2; and the following sequence:
X[0] = 1 X[1] = 5 X[2] = 7 X[3] = 4 X[4] = 2 X[5] = 8has two medians: 4 and 5.
Note that sequences of odd length have only one median, which is equal to X[N/2] after sorting X. In this problem we consider medians of sequences of odd length only.
Write a function:
class Solution { public int solution(int[] A, int[] B, int[] P, int[] Q, int[] R, int[] S); }
that, given:
- two non-empty arrays, A (consisting of N integers) and B (consisting of M integers), both sorted in ascending order
- two arrays P and Q, each consisting of K indices of array A, such that 0 ≤ P[I] ≤ Q[I] < N for 0 ≤ I < K
- two arrays R and S, each consisting of K indices of array B, such that 0 ≤ R[I] ≤ S[I] < M for 0 ≤ I < K
computes medians of K sequences of the form:
A[P[I]], A[P[I]+1], ..., A[Q[I]-1], A[Q[I]], B[R[I]], B[R[I]+1], ..., B[S[I]-1], B[S[I]]for 0 ≤ I < K, and returns the median of all such medians.
For example, given the following arrays:
A[0] = -2 A[1] = 4 A[2] = 10 A[3] = 13 B[0] = 5 B[1] = 6 B[2] = 8 B[3] = 12 B[4] = 13 P[0] = 2 P[1] = 1 P[2] = 0 Q[0] = 3 Q[1] = 2 Q[2] = 3 R[0] = 0 R[1] = 0 R[2] = 1 S[0] = 4 S[1] = 0 S[2] = 3the function should return 8, since:
- the median of [10, 13, 5, 6, 8, 12, 13] equals 10,
- the median of [4, 10, 5] equals 5,
- the median of [−2, 4, 10, 13, 6, 8, 12] equals 8, and
- the median of [10, 5, 8] equals 8.
Write an efficient algorithm for the following assumptions:
- N and M are integers within the range [1..100,000];
- K is an integer within the range [1..10,000];
- each element of arrays A and B is an integer within the range [−1,000,000,000..1,000,000,000];
- array A is sorted in non-decreasing order;
- array B is sorted in non-decreasing order;
- each element of arrays P and Q is an integer within the range [0..N-1];
- each element of arrays R and S is an integer within the range [0..M-1];
- P[i] ≤ Q[i] and R[i] ≤ S[i] for 0 ≤ i < K;
- K is odd and so is Q[i]−P[i]+R[i]−S[i] for 0 ≤ i < K.
The median of a sequence of numbers X[0], X[1], ..., X[N] is the middle element in terms of their values. More formally, the median of X[0], X[1], ..., X[N] is an element X[I] of the sequence, such that at most half of the elements are larger than X[I] and at most half of the elements are smaller than X[I]. For example, the median of the following sequence:
X[0] = 7 X[1] = 2 X[2] = 5 X[3] = 2 X[4] = 8is 5; the median of the following sequence:
X[0] = 2 X[1] = 2 X[2] = 5 X[3] = 2is 2; and the following sequence:
X[0] = 1 X[1] = 5 X[2] = 7 X[3] = 4 X[4] = 2 X[5] = 8has two medians: 4 and 5.
Note that sequences of odd length have only one median, which is equal to X[N/2] after sorting X. In this problem we consider medians of sequences of odd length only.
Write a function:
function solution(A, B, P, Q, R, S);
that, given:
- two non-empty arrays, A (consisting of N integers) and B (consisting of M integers), both sorted in ascending order
- two arrays P and Q, each consisting of K indices of array A, such that 0 ≤ P[I] ≤ Q[I] < N for 0 ≤ I < K
- two arrays R and S, each consisting of K indices of array B, such that 0 ≤ R[I] ≤ S[I] < M for 0 ≤ I < K
computes medians of K sequences of the form:
A[P[I]], A[P[I]+1], ..., A[Q[I]-1], A[Q[I]], B[R[I]], B[R[I]+1], ..., B[S[I]-1], B[S[I]]for 0 ≤ I < K, and returns the median of all such medians.
For example, given the following arrays:
A[0] = -2 A[1] = 4 A[2] = 10 A[3] = 13 B[0] = 5 B[1] = 6 B[2] = 8 B[3] = 12 B[4] = 13 P[0] = 2 P[1] = 1 P[2] = 0 Q[0] = 3 Q[1] = 2 Q[2] = 3 R[0] = 0 R[1] = 0 R[2] = 1 S[0] = 4 S[1] = 0 S[2] = 3the function should return 8, since:
- the median of [10, 13, 5, 6, 8, 12, 13] equals 10,
- the median of [4, 10, 5] equals 5,
- the median of [−2, 4, 10, 13, 6, 8, 12] equals 8, and
- the median of [10, 5, 8] equals 8.
Write an efficient algorithm for the following assumptions:
- N and M are integers within the range [1..100,000];
- K is an integer within the range [1..10,000];
- each element of arrays A and B is an integer within the range [−1,000,000,000..1,000,000,000];
- array A is sorted in non-decreasing order;
- array B is sorted in non-decreasing order;
- each element of arrays P and Q is an integer within the range [0..N-1];
- each element of arrays R and S is an integer within the range [0..M-1];
- P[i] ≤ Q[i] and R[i] ≤ S[i] for 0 ≤ i < K;
- K is odd and so is Q[i]−P[i]+R[i]−S[i] for 0 ≤ i < K.
The median of a sequence of numbers X[0], X[1], ..., X[N] is the middle element in terms of their values. More formally, the median of X[0], X[1], ..., X[N] is an element X[I] of the sequence, such that at most half of the elements are larger than X[I] and at most half of the elements are smaller than X[I]. For example, the median of the following sequence:
X[0] = 7 X[1] = 2 X[2] = 5 X[3] = 2 X[4] = 8is 5; the median of the following sequence:
X[0] = 2 X[1] = 2 X[2] = 5 X[3] = 2is 2; and the following sequence:
X[0] = 1 X[1] = 5 X[2] = 7 X[3] = 4 X[4] = 2 X[5] = 8has two medians: 4 and 5.
Note that sequences of odd length have only one median, which is equal to X[N/2] after sorting X. In this problem we consider medians of sequences of odd length only.
Write a function:
fun solution(A: IntArray, B: IntArray, P: IntArray, Q: IntArray, R: IntArray, S: IntArray): Int
that, given:
- two non-empty arrays, A (consisting of N integers) and B (consisting of M integers), both sorted in ascending order
- two arrays P and Q, each consisting of K indices of array A, such that 0 ≤ P[I] ≤ Q[I] < N for 0 ≤ I < K
- two arrays R and S, each consisting of K indices of array B, such that 0 ≤ R[I] ≤ S[I] < M for 0 ≤ I < K
computes medians of K sequences of the form:
A[P[I]], A[P[I]+1], ..., A[Q[I]-1], A[Q[I]], B[R[I]], B[R[I]+1], ..., B[S[I]-1], B[S[I]]for 0 ≤ I < K, and returns the median of all such medians.
For example, given the following arrays:
A[0] = -2 A[1] = 4 A[2] = 10 A[3] = 13 B[0] = 5 B[1] = 6 B[2] = 8 B[3] = 12 B[4] = 13 P[0] = 2 P[1] = 1 P[2] = 0 Q[0] = 3 Q[1] = 2 Q[2] = 3 R[0] = 0 R[1] = 0 R[2] = 1 S[0] = 4 S[1] = 0 S[2] = 3the function should return 8, since:
- the median of [10, 13, 5, 6, 8, 12, 13] equals 10,
- the median of [4, 10, 5] equals 5,
- the median of [−2, 4, 10, 13, 6, 8, 12] equals 8, and
- the median of [10, 5, 8] equals 8.
Write an efficient algorithm for the following assumptions:
- N and M are integers within the range [1..100,000];
- K is an integer within the range [1..10,000];
- each element of arrays A and B is an integer within the range [−1,000,000,000..1,000,000,000];
- array A is sorted in non-decreasing order;
- array B is sorted in non-decreasing order;
- each element of arrays P and Q is an integer within the range [0..N-1];
- each element of arrays R and S is an integer within the range [0..M-1];
- P[i] ≤ Q[i] and R[i] ≤ S[i] for 0 ≤ i < K;
- K is odd and so is Q[i]−P[i]+R[i]−S[i] for 0 ≤ i < K.
The median of a sequence of numbers X[0], X[1], ..., X[N] is the middle element in terms of their values. More formally, the median of X[0], X[1], ..., X[N] is an element X[I] of the sequence, such that at most half of the elements are larger than X[I] and at most half of the elements are smaller than X[I]. For example, the median of the following sequence:
X[0] = 7 X[1] = 2 X[2] = 5 X[3] = 2 X[4] = 8is 5; the median of the following sequence:
X[0] = 2 X[1] = 2 X[2] = 5 X[3] = 2is 2; and the following sequence:
X[0] = 1 X[1] = 5 X[2] = 7 X[3] = 4 X[4] = 2 X[5] = 8has two medians: 4 and 5.
Note that sequences of odd length have only one median, which is equal to X[N/2] after sorting X. In this problem we consider medians of sequences of odd length only.
Write a function:
function solution(A, B, P, Q, R, S)
that, given:
- two non-empty arrays, A (consisting of N integers) and B (consisting of M integers), both sorted in ascending order
- two arrays P and Q, each consisting of K indices of array A, such that 0 ≤ P[I] ≤ Q[I] < N for 0 ≤ I < K
- two arrays R and S, each consisting of K indices of array B, such that 0 ≤ R[I] ≤ S[I] < M for 0 ≤ I < K
computes medians of K sequences of the form:
A[P[I]], A[P[I]+1], ..., A[Q[I]-1], A[Q[I]], B[R[I]], B[R[I]+1], ..., B[S[I]-1], B[S[I]]for 0 ≤ I < K, and returns the median of all such medians.
For example, given the following arrays:
A[0] = -2 A[1] = 4 A[2] = 10 A[3] = 13 B[0] = 5 B[1] = 6 B[2] = 8 B[3] = 12 B[4] = 13 P[0] = 2 P[1] = 1 P[2] = 0 Q[0] = 3 Q[1] = 2 Q[2] = 3 R[0] = 0 R[1] = 0 R[2] = 1 S[0] = 4 S[1] = 0 S[2] = 3the function should return 8, since:
- the median of [10, 13, 5, 6, 8, 12, 13] equals 10,
- the median of [4, 10, 5] equals 5,
- the median of [−2, 4, 10, 13, 6, 8, 12] equals 8, and
- the median of [10, 5, 8] equals 8.
Write an efficient algorithm for the following assumptions:
- N and M are integers within the range [1..100,000];
- K is an integer within the range [1..10,000];
- each element of arrays A and B is an integer within the range [−1,000,000,000..1,000,000,000];
- array A is sorted in non-decreasing order;
- array B is sorted in non-decreasing order;
- each element of arrays P and Q is an integer within the range [0..N-1];
- each element of arrays R and S is an integer within the range [0..M-1];
- P[i] ≤ Q[i] and R[i] ≤ S[i] for 0 ≤ i < K;
- K is odd and so is Q[i]−P[i]+R[i]−S[i] for 0 ≤ i < K.
Note: All arrays in this task are zero-indexed, unlike the common Lua convention. You can use #A to get the length of the array A.
The median of a sequence of numbers X[0], X[1], ..., X[N] is the middle element in terms of their values. More formally, the median of X[0], X[1], ..., X[N] is an element X[I] of the sequence, such that at most half of the elements are larger than X[I] and at most half of the elements are smaller than X[I]. For example, the median of the following sequence:
X[0] = 7 X[1] = 2 X[2] = 5 X[3] = 2 X[4] = 8is 5; the median of the following sequence:
X[0] = 2 X[1] = 2 X[2] = 5 X[3] = 2is 2; and the following sequence:
X[0] = 1 X[1] = 5 X[2] = 7 X[3] = 4 X[4] = 2 X[5] = 8has two medians: 4 and 5.
Note that sequences of odd length have only one median, which is equal to X[N/2] after sorting X. In this problem we consider medians of sequences of odd length only.
Write a function:
int solution(NSMutableArray *A, NSMutableArray *B, NSMutableArray *P, NSMutableArray *Q, NSMutableArray *R, NSMutableArray *S);
that, given:
- two non-empty arrays, A (consisting of N integers) and B (consisting of M integers), both sorted in ascending order
- two arrays P and Q, each consisting of K indices of array A, such that 0 ≤ P[I] ≤ Q[I] < N for 0 ≤ I < K
- two arrays R and S, each consisting of K indices of array B, such that 0 ≤ R[I] ≤ S[I] < M for 0 ≤ I < K
computes medians of K sequences of the form:
A[P[I]], A[P[I]+1], ..., A[Q[I]-1], A[Q[I]], B[R[I]], B[R[I]+1], ..., B[S[I]-1], B[S[I]]for 0 ≤ I < K, and returns the median of all such medians.
For example, given the following arrays:
A[0] = -2 A[1] = 4 A[2] = 10 A[3] = 13 B[0] = 5 B[1] = 6 B[2] = 8 B[3] = 12 B[4] = 13 P[0] = 2 P[1] = 1 P[2] = 0 Q[0] = 3 Q[1] = 2 Q[2] = 3 R[0] = 0 R[1] = 0 R[2] = 1 S[0] = 4 S[1] = 0 S[2] = 3the function should return 8, since:
- the median of [10, 13, 5, 6, 8, 12, 13] equals 10,
- the median of [4, 10, 5] equals 5,
- the median of [−2, 4, 10, 13, 6, 8, 12] equals 8, and
- the median of [10, 5, 8] equals 8.
Write an efficient algorithm for the following assumptions:
- N and M are integers within the range [1..100,000];
- K is an integer within the range [1..10,000];
- each element of arrays A and B is an integer within the range [−1,000,000,000..1,000,000,000];
- array A is sorted in non-decreasing order;
- array B is sorted in non-decreasing order;
- each element of arrays P and Q is an integer within the range [0..N-1];
- each element of arrays R and S is an integer within the range [0..M-1];
- P[i] ≤ Q[i] and R[i] ≤ S[i] for 0 ≤ i < K;
- K is odd and so is Q[i]−P[i]+R[i]−S[i] for 0 ≤ i < K.
The median of a sequence of numbers X[0], X[1], ..., X[N] is the middle element in terms of their values. More formally, the median of X[0], X[1], ..., X[N] is an element X[I] of the sequence, such that at most half of the elements are larger than X[I] and at most half of the elements are smaller than X[I]. For example, the median of the following sequence:
X[0] = 7 X[1] = 2 X[2] = 5 X[3] = 2 X[4] = 8is 5; the median of the following sequence:
X[0] = 2 X[1] = 2 X[2] = 5 X[3] = 2is 2; and the following sequence:
X[0] = 1 X[1] = 5 X[2] = 7 X[3] = 4 X[4] = 2 X[5] = 8has two medians: 4 and 5.
Note that sequences of odd length have only one median, which is equal to X[N/2] after sorting X. In this problem we consider medians of sequences of odd length only.
Write a function:
function solution(A: array of longint; N: longint; B: array of longint; M: longint; P: array of longint; Q: array of longint; R: array of longint; S: array of longint; K: longint): longint;
that, given:
- two non-empty arrays, A (consisting of N integers) and B (consisting of M integers), both sorted in ascending order
- two arrays P and Q, each consisting of K indices of array A, such that 0 ≤ P[I] ≤ Q[I] < N for 0 ≤ I < K
- two arrays R and S, each consisting of K indices of array B, such that 0 ≤ R[I] ≤ S[I] < M for 0 ≤ I < K
computes medians of K sequences of the form:
A[P[I]], A[P[I]+1], ..., A[Q[I]-1], A[Q[I]], B[R[I]], B[R[I]+1], ..., B[S[I]-1], B[S[I]]for 0 ≤ I < K, and returns the median of all such medians.
For example, given the following arrays:
A[0] = -2 A[1] = 4 A[2] = 10 A[3] = 13 B[0] = 5 B[1] = 6 B[2] = 8 B[3] = 12 B[4] = 13 P[0] = 2 P[1] = 1 P[2] = 0 Q[0] = 3 Q[1] = 2 Q[2] = 3 R[0] = 0 R[1] = 0 R[2] = 1 S[0] = 4 S[1] = 0 S[2] = 3the function should return 8, since:
- the median of [10, 13, 5, 6, 8, 12, 13] equals 10,
- the median of [4, 10, 5] equals 5,
- the median of [−2, 4, 10, 13, 6, 8, 12] equals 8, and
- the median of [10, 5, 8] equals 8.
Write an efficient algorithm for the following assumptions:
- N and M are integers within the range [1..100,000];
- K is an integer within the range [1..10,000];
- each element of arrays A and B is an integer within the range [−1,000,000,000..1,000,000,000];
- array A is sorted in non-decreasing order;
- array B is sorted in non-decreasing order;
- each element of arrays P and Q is an integer within the range [0..N-1];
- each element of arrays R and S is an integer within the range [0..M-1];
- P[i] ≤ Q[i] and R[i] ≤ S[i] for 0 ≤ i < K;
- K is odd and so is Q[i]−P[i]+R[i]−S[i] for 0 ≤ i < K.
The median of a sequence of numbers X[0], X[1], ..., X[N] is the middle element in terms of their values. More formally, the median of X[0], X[1], ..., X[N] is an element X[I] of the sequence, such that at most half of the elements are larger than X[I] and at most half of the elements are smaller than X[I]. For example, the median of the following sequence:
X[0] = 7 X[1] = 2 X[2] = 5 X[3] = 2 X[4] = 8is 5; the median of the following sequence:
X[0] = 2 X[1] = 2 X[2] = 5 X[3] = 2is 2; and the following sequence:
X[0] = 1 X[1] = 5 X[2] = 7 X[3] = 4 X[4] = 2 X[5] = 8has two medians: 4 and 5.
Note that sequences of odd length have only one median, which is equal to X[N/2] after sorting X. In this problem we consider medians of sequences of odd length only.
Write a function:
function solution($A, $B, $P, $Q, $R, $S);
that, given:
- two non-empty arrays, A (consisting of N integers) and B (consisting of M integers), both sorted in ascending order
- two arrays P and Q, each consisting of K indices of array A, such that 0 ≤ P[I] ≤ Q[I] < N for 0 ≤ I < K
- two arrays R and S, each consisting of K indices of array B, such that 0 ≤ R[I] ≤ S[I] < M for 0 ≤ I < K
computes medians of K sequences of the form:
A[P[I]], A[P[I]+1], ..., A[Q[I]-1], A[Q[I]], B[R[I]], B[R[I]+1], ..., B[S[I]-1], B[S[I]]for 0 ≤ I < K, and returns the median of all such medians.
For example, given the following arrays:
A[0] = -2 A[1] = 4 A[2] = 10 A[3] = 13 B[0] = 5 B[1] = 6 B[2] = 8 B[3] = 12 B[4] = 13 P[0] = 2 P[1] = 1 P[2] = 0 Q[0] = 3 Q[1] = 2 Q[2] = 3 R[0] = 0 R[1] = 0 R[2] = 1 S[0] = 4 S[1] = 0 S[2] = 3the function should return 8, since:
- the median of [10, 13, 5, 6, 8, 12, 13] equals 10,
- the median of [4, 10, 5] equals 5,
- the median of [−2, 4, 10, 13, 6, 8, 12] equals 8, and
- the median of [10, 5, 8] equals 8.
Write an efficient algorithm for the following assumptions:
- N and M are integers within the range [1..100,000];
- K is an integer within the range [1..10,000];
- each element of arrays A and B is an integer within the range [−1,000,000,000..1,000,000,000];
- array A is sorted in non-decreasing order;
- array B is sorted in non-decreasing order;
- each element of arrays P and Q is an integer within the range [0..N-1];
- each element of arrays R and S is an integer within the range [0..M-1];
- P[i] ≤ Q[i] and R[i] ≤ S[i] for 0 ≤ i < K;
- K is odd and so is Q[i]−P[i]+R[i]−S[i] for 0 ≤ i < K.
The median of a sequence of numbers X[0], X[1], ..., X[N] is the middle element in terms of their values. More formally, the median of X[0], X[1], ..., X[N] is an element X[I] of the sequence, such that at most half of the elements are larger than X[I] and at most half of the elements are smaller than X[I]. For example, the median of the following sequence:
X[0] = 7 X[1] = 2 X[2] = 5 X[3] = 2 X[4] = 8is 5; the median of the following sequence:
X[0] = 2 X[1] = 2 X[2] = 5 X[3] = 2is 2; and the following sequence:
X[0] = 1 X[1] = 5 X[2] = 7 X[3] = 4 X[4] = 2 X[5] = 8has two medians: 4 and 5.
Note that sequences of odd length have only one median, which is equal to X[N/2] after sorting X. In this problem we consider medians of sequences of odd length only.
Write a function:
sub solution { my ($A, $B, $P, $Q, $R, $S) = @_; my @A = @$A; my @B = @$B; my @P = @$P; my @Q = @$Q; my @R = @$R; my @S = @$S; ... }
that, given:
- two non-empty arrays, A (consisting of N integers) and B (consisting of M integers), both sorted in ascending order
- two arrays P and Q, each consisting of K indices of array A, such that 0 ≤ P[I] ≤ Q[I] < N for 0 ≤ I < K
- two arrays R and S, each consisting of K indices of array B, such that 0 ≤ R[I] ≤ S[I] < M for 0 ≤ I < K
computes medians of K sequences of the form:
A[P[I]], A[P[I]+1], ..., A[Q[I]-1], A[Q[I]], B[R[I]], B[R[I]+1], ..., B[S[I]-1], B[S[I]]for 0 ≤ I < K, and returns the median of all such medians.
For example, given the following arrays:
A[0] = -2 A[1] = 4 A[2] = 10 A[3] = 13 B[0] = 5 B[1] = 6 B[2] = 8 B[3] = 12 B[4] = 13 P[0] = 2 P[1] = 1 P[2] = 0 Q[0] = 3 Q[1] = 2 Q[2] = 3 R[0] = 0 R[1] = 0 R[2] = 1 S[0] = 4 S[1] = 0 S[2] = 3the function should return 8, since:
- the median of [10, 13, 5, 6, 8, 12, 13] equals 10,
- the median of [4, 10, 5] equals 5,
- the median of [−2, 4, 10, 13, 6, 8, 12] equals 8, and
- the median of [10, 5, 8] equals 8.
Write an efficient algorithm for the following assumptions:
- N and M are integers within the range [1..100,000];
- K is an integer within the range [1..10,000];
- each element of arrays A and B is an integer within the range [−1,000,000,000..1,000,000,000];
- array A is sorted in non-decreasing order;
- array B is sorted in non-decreasing order;
- each element of arrays P and Q is an integer within the range [0..N-1];
- each element of arrays R and S is an integer within the range [0..M-1];
- P[i] ≤ Q[i] and R[i] ≤ S[i] for 0 ≤ i < K;
- K is odd and so is Q[i]−P[i]+R[i]−S[i] for 0 ≤ i < K.
The median of a sequence of numbers X[0], X[1], ..., X[N] is the middle element in terms of their values. More formally, the median of X[0], X[1], ..., X[N] is an element X[I] of the sequence, such that at most half of the elements are larger than X[I] and at most half of the elements are smaller than X[I]. For example, the median of the following sequence:
X[0] = 7 X[1] = 2 X[2] = 5 X[3] = 2 X[4] = 8is 5; the median of the following sequence:
X[0] = 2 X[1] = 2 X[2] = 5 X[3] = 2is 2; and the following sequence:
X[0] = 1 X[1] = 5 X[2] = 7 X[3] = 4 X[4] = 2 X[5] = 8has two medians: 4 and 5.
Note that sequences of odd length have only one median, which is equal to X[N/2] after sorting X. In this problem we consider medians of sequences of odd length only.
Write a function:
def solution(A, B, P, Q, R, S)
that, given:
- two non-empty arrays, A (consisting of N integers) and B (consisting of M integers), both sorted in ascending order
- two arrays P and Q, each consisting of K indices of array A, such that 0 ≤ P[I] ≤ Q[I] < N for 0 ≤ I < K
- two arrays R and S, each consisting of K indices of array B, such that 0 ≤ R[I] ≤ S[I] < M for 0 ≤ I < K
computes medians of K sequences of the form:
A[P[I]], A[P[I]+1], ..., A[Q[I]-1], A[Q[I]], B[R[I]], B[R[I]+1], ..., B[S[I]-1], B[S[I]]for 0 ≤ I < K, and returns the median of all such medians.
For example, given the following arrays:
A[0] = -2 A[1] = 4 A[2] = 10 A[3] = 13 B[0] = 5 B[1] = 6 B[2] = 8 B[3] = 12 B[4] = 13 P[0] = 2 P[1] = 1 P[2] = 0 Q[0] = 3 Q[1] = 2 Q[2] = 3 R[0] = 0 R[1] = 0 R[2] = 1 S[0] = 4 S[1] = 0 S[2] = 3the function should return 8, since:
- the median of [10, 13, 5, 6, 8, 12, 13] equals 10,
- the median of [4, 10, 5] equals 5,
- the median of [−2, 4, 10, 13, 6, 8, 12] equals 8, and
- the median of [10, 5, 8] equals 8.
Write an efficient algorithm for the following assumptions:
- N and M are integers within the range [1..100,000];
- K is an integer within the range [1..10,000];
- each element of arrays A and B is an integer within the range [−1,000,000,000..1,000,000,000];
- array A is sorted in non-decreasing order;
- array B is sorted in non-decreasing order;
- each element of arrays P and Q is an integer within the range [0..N-1];
- each element of arrays R and S is an integer within the range [0..M-1];
- P[i] ≤ Q[i] and R[i] ≤ S[i] for 0 ≤ i < K;
- K is odd and so is Q[i]−P[i]+R[i]−S[i] for 0 ≤ i < K.
The median of a sequence of numbers X[0], X[1], ..., X[N] is the middle element in terms of their values. More formally, the median of X[0], X[1], ..., X[N] is an element X[I] of the sequence, such that at most half of the elements are larger than X[I] and at most half of the elements are smaller than X[I]. For example, the median of the following sequence:
X[0] = 7 X[1] = 2 X[2] = 5 X[3] = 2 X[4] = 8is 5; the median of the following sequence:
X[0] = 2 X[1] = 2 X[2] = 5 X[3] = 2is 2; and the following sequence:
X[0] = 1 X[1] = 5 X[2] = 7 X[3] = 4 X[4] = 2 X[5] = 8has two medians: 4 and 5.
Note that sequences of odd length have only one median, which is equal to X[N/2] after sorting X. In this problem we consider medians of sequences of odd length only.
Write a function:
def solution(a, b, p, q, r, s)
that, given:
- two non-empty arrays, A (consisting of N integers) and B (consisting of M integers), both sorted in ascending order
- two arrays P and Q, each consisting of K indices of array A, such that 0 ≤ P[I] ≤ Q[I] < N for 0 ≤ I < K
- two arrays R and S, each consisting of K indices of array B, such that 0 ≤ R[I] ≤ S[I] < M for 0 ≤ I < K
computes medians of K sequences of the form:
A[P[I]], A[P[I]+1], ..., A[Q[I]-1], A[Q[I]], B[R[I]], B[R[I]+1], ..., B[S[I]-1], B[S[I]]for 0 ≤ I < K, and returns the median of all such medians.
For example, given the following arrays:
A[0] = -2 A[1] = 4 A[2] = 10 A[3] = 13 B[0] = 5 B[1] = 6 B[2] = 8 B[3] = 12 B[4] = 13 P[0] = 2 P[1] = 1 P[2] = 0 Q[0] = 3 Q[1] = 2 Q[2] = 3 R[0] = 0 R[1] = 0 R[2] = 1 S[0] = 4 S[1] = 0 S[2] = 3the function should return 8, since:
- the median of [10, 13, 5, 6, 8, 12, 13] equals 10,
- the median of [4, 10, 5] equals 5,
- the median of [−2, 4, 10, 13, 6, 8, 12] equals 8, and
- the median of [10, 5, 8] equals 8.
Write an efficient algorithm for the following assumptions:
- N and M are integers within the range [1..100,000];
- K is an integer within the range [1..10,000];
- each element of arrays A and B is an integer within the range [−1,000,000,000..1,000,000,000];
- array A is sorted in non-decreasing order;
- array B is sorted in non-decreasing order;
- each element of arrays P and Q is an integer within the range [0..N-1];
- each element of arrays R and S is an integer within the range [0..M-1];
- P[i] ≤ Q[i] and R[i] ≤ S[i] for 0 ≤ i < K;
- K is odd and so is Q[i]−P[i]+R[i]−S[i] for 0 ≤ i < K.
The median of a sequence of numbers X[0], X[1], ..., X[N] is the middle element in terms of their values. More formally, the median of X[0], X[1], ..., X[N] is an element X[I] of the sequence, such that at most half of the elements are larger than X[I] and at most half of the elements are smaller than X[I]. For example, the median of the following sequence:
X[0] = 7 X[1] = 2 X[2] = 5 X[3] = 2 X[4] = 8is 5; the median of the following sequence:
X[0] = 2 X[1] = 2 X[2] = 5 X[3] = 2is 2; and the following sequence:
X[0] = 1 X[1] = 5 X[2] = 7 X[3] = 4 X[4] = 2 X[5] = 8has two medians: 4 and 5.
Note that sequences of odd length have only one median, which is equal to X[N/2] after sorting X. In this problem we consider medians of sequences of odd length only.
Write a function:
object Solution { def solution(a: Array[Int], b: Array[Int], p: Array[Int], q: Array[Int], r: Array[Int], s: Array[Int]): Int }
that, given:
- two non-empty arrays, A (consisting of N integers) and B (consisting of M integers), both sorted in ascending order
- two arrays P and Q, each consisting of K indices of array A, such that 0 ≤ P[I] ≤ Q[I] < N for 0 ≤ I < K
- two arrays R and S, each consisting of K indices of array B, such that 0 ≤ R[I] ≤ S[I] < M for 0 ≤ I < K
computes medians of K sequences of the form:
A[P[I]], A[P[I]+1], ..., A[Q[I]-1], A[Q[I]], B[R[I]], B[R[I]+1], ..., B[S[I]-1], B[S[I]]for 0 ≤ I < K, and returns the median of all such medians.
For example, given the following arrays:
A[0] = -2 A[1] = 4 A[2] = 10 A[3] = 13 B[0] = 5 B[1] = 6 B[2] = 8 B[3] = 12 B[4] = 13 P[0] = 2 P[1] = 1 P[2] = 0 Q[0] = 3 Q[1] = 2 Q[2] = 3 R[0] = 0 R[1] = 0 R[2] = 1 S[0] = 4 S[1] = 0 S[2] = 3the function should return 8, since:
- the median of [10, 13, 5, 6, 8, 12, 13] equals 10,
- the median of [4, 10, 5] equals 5,
- the median of [−2, 4, 10, 13, 6, 8, 12] equals 8, and
- the median of [10, 5, 8] equals 8.
Write an efficient algorithm for the following assumptions:
- N and M are integers within the range [1..100,000];
- K is an integer within the range [1..10,000];
- each element of arrays A and B is an integer within the range [−1,000,000,000..1,000,000,000];
- array A is sorted in non-decreasing order;
- array B is sorted in non-decreasing order;
- each element of arrays P and Q is an integer within the range [0..N-1];
- each element of arrays R and S is an integer within the range [0..M-1];
- P[i] ≤ Q[i] and R[i] ≤ S[i] for 0 ≤ i < K;
- K is odd and so is Q[i]−P[i]+R[i]−S[i] for 0 ≤ i < K.
The median of a sequence of numbers X[0], X[1], ..., X[N] is the middle element in terms of their values. More formally, the median of X[0], X[1], ..., X[N] is an element X[I] of the sequence, such that at most half of the elements are larger than X[I] and at most half of the elements are smaller than X[I]. For example, the median of the following sequence:
X[0] = 7 X[1] = 2 X[2] = 5 X[3] = 2 X[4] = 8is 5; the median of the following sequence:
X[0] = 2 X[1] = 2 X[2] = 5 X[3] = 2is 2; and the following sequence:
X[0] = 1 X[1] = 5 X[2] = 7 X[3] = 4 X[4] = 2 X[5] = 8has two medians: 4 and 5.
Note that sequences of odd length have only one median, which is equal to X[N/2] after sorting X. In this problem we consider medians of sequences of odd length only.
Write a function:
public func solution(_ A : inout [Int], _ B : inout [Int], _ P : inout [Int], _ Q : inout [Int], _ R : inout [Int], _ S : inout [Int]) -> Int
that, given:
- two non-empty arrays, A (consisting of N integers) and B (consisting of M integers), both sorted in ascending order
- two arrays P and Q, each consisting of K indices of array A, such that 0 ≤ P[I] ≤ Q[I] < N for 0 ≤ I < K
- two arrays R and S, each consisting of K indices of array B, such that 0 ≤ R[I] ≤ S[I] < M for 0 ≤ I < K
computes medians of K sequences of the form:
A[P[I]], A[P[I]+1], ..., A[Q[I]-1], A[Q[I]], B[R[I]], B[R[I]+1], ..., B[S[I]-1], B[S[I]]for 0 ≤ I < K, and returns the median of all such medians.
For example, given the following arrays:
A[0] = -2 A[1] = 4 A[2] = 10 A[3] = 13 B[0] = 5 B[1] = 6 B[2] = 8 B[3] = 12 B[4] = 13 P[0] = 2 P[1] = 1 P[2] = 0 Q[0] = 3 Q[1] = 2 Q[2] = 3 R[0] = 0 R[1] = 0 R[2] = 1 S[0] = 4 S[1] = 0 S[2] = 3the function should return 8, since:
- the median of [10, 13, 5, 6, 8, 12, 13] equals 10,
- the median of [4, 10, 5] equals 5,
- the median of [−2, 4, 10, 13, 6, 8, 12] equals 8, and
- the median of [10, 5, 8] equals 8.
Write an efficient algorithm for the following assumptions:
- N and M are integers within the range [1..100,000];
- K is an integer within the range [1..10,000];
- each element of arrays A and B is an integer within the range [−1,000,000,000..1,000,000,000];
- array A is sorted in non-decreasing order;
- array B is sorted in non-decreasing order;
- each element of arrays P and Q is an integer within the range [0..N-1];
- each element of arrays R and S is an integer within the range [0..M-1];
- P[i] ≤ Q[i] and R[i] ≤ S[i] for 0 ≤ i < K;
- K is odd and so is Q[i]−P[i]+R[i]−S[i] for 0 ≤ i < K.
The median of a sequence of numbers X[0], X[1], ..., X[N] is the middle element in terms of their values. More formally, the median of X[0], X[1], ..., X[N] is an element X[I] of the sequence, such that at most half of the elements are larger than X[I] and at most half of the elements are smaller than X[I]. For example, the median of the following sequence:
X[0] = 7 X[1] = 2 X[2] = 5 X[3] = 2 X[4] = 8is 5; the median of the following sequence:
X[0] = 2 X[1] = 2 X[2] = 5 X[3] = 2is 2; and the following sequence:
X[0] = 1 X[1] = 5 X[2] = 7 X[3] = 4 X[4] = 2 X[5] = 8has two medians: 4 and 5.
Note that sequences of odd length have only one median, which is equal to X[N/2] after sorting X. In this problem we consider medians of sequences of odd length only.
Write a function:
function solution(A: number[], B: number[], P: number[], Q: number[], R: number[], S: number[]): number;
that, given:
- two non-empty arrays, A (consisting of N integers) and B (consisting of M integers), both sorted in ascending order
- two arrays P and Q, each consisting of K indices of array A, such that 0 ≤ P[I] ≤ Q[I] < N for 0 ≤ I < K
- two arrays R and S, each consisting of K indices of array B, such that 0 ≤ R[I] ≤ S[I] < M for 0 ≤ I < K
computes medians of K sequences of the form:
A[P[I]], A[P[I]+1], ..., A[Q[I]-1], A[Q[I]], B[R[I]], B[R[I]+1], ..., B[S[I]-1], B[S[I]]for 0 ≤ I < K, and returns the median of all such medians.
For example, given the following arrays:
A[0] = -2 A[1] = 4 A[2] = 10 A[3] = 13 B[0] = 5 B[1] = 6 B[2] = 8 B[3] = 12 B[4] = 13 P[0] = 2 P[1] = 1 P[2] = 0 Q[0] = 3 Q[1] = 2 Q[2] = 3 R[0] = 0 R[1] = 0 R[2] = 1 S[0] = 4 S[1] = 0 S[2] = 3the function should return 8, since:
- the median of [10, 13, 5, 6, 8, 12, 13] equals 10,
- the median of [4, 10, 5] equals 5,
- the median of [−2, 4, 10, 13, 6, 8, 12] equals 8, and
- the median of [10, 5, 8] equals 8.
Write an efficient algorithm for the following assumptions:
- N and M are integers within the range [1..100,000];
- K is an integer within the range [1..10,000];
- each element of arrays A and B is an integer within the range [−1,000,000,000..1,000,000,000];
- array A is sorted in non-decreasing order;
- array B is sorted in non-decreasing order;
- each element of arrays P and Q is an integer within the range [0..N-1];
- each element of arrays R and S is an integer within the range [0..M-1];
- P[i] ≤ Q[i] and R[i] ≤ S[i] for 0 ≤ i < K;
- K is odd and so is Q[i]−P[i]+R[i]−S[i] for 0 ≤ i < K.
The median of a sequence of numbers X[0], X[1], ..., X[N] is the middle element in terms of their values. More formally, the median of X[0], X[1], ..., X[N] is an element X[I] of the sequence, such that at most half of the elements are larger than X[I] and at most half of the elements are smaller than X[I]. For example, the median of the following sequence:
X[0] = 7 X[1] = 2 X[2] = 5 X[3] = 2 X[4] = 8is 5; the median of the following sequence:
X[0] = 2 X[1] = 2 X[2] = 5 X[3] = 2is 2; and the following sequence:
X[0] = 1 X[1] = 5 X[2] = 7 X[3] = 4 X[4] = 2 X[5] = 8has two medians: 4 and 5.
Note that sequences of odd length have only one median, which is equal to X[N/2] after sorting X. In this problem we consider medians of sequences of odd length only.
Write a function:
Private Function solution(A As Integer(), B As Integer(), P As Integer(), Q As Integer(), R As Integer(), S As Integer()) As Integer
that, given:
- two non-empty arrays, A (consisting of N integers) and B (consisting of M integers), both sorted in ascending order
- two arrays P and Q, each consisting of K indices of array A, such that 0 ≤ P[I] ≤ Q[I] < N for 0 ≤ I < K
- two arrays R and S, each consisting of K indices of array B, such that 0 ≤ R[I] ≤ S[I] < M for 0 ≤ I < K
computes medians of K sequences of the form:
A[P[I]], A[P[I]+1], ..., A[Q[I]-1], A[Q[I]], B[R[I]], B[R[I]+1], ..., B[S[I]-1], B[S[I]]for 0 ≤ I < K, and returns the median of all such medians.
For example, given the following arrays:
A[0] = -2 A[1] = 4 A[2] = 10 A[3] = 13 B[0] = 5 B[1] = 6 B[2] = 8 B[3] = 12 B[4] = 13 P[0] = 2 P[1] = 1 P[2] = 0 Q[0] = 3 Q[1] = 2 Q[2] = 3 R[0] = 0 R[1] = 0 R[2] = 1 S[0] = 4 S[1] = 0 S[2] = 3the function should return 8, since:
- the median of [10, 13, 5, 6, 8, 12, 13] equals 10,
- the median of [4, 10, 5] equals 5,
- the median of [−2, 4, 10, 13, 6, 8, 12] equals 8, and
- the median of [10, 5, 8] equals 8.
Write an efficient algorithm for the following assumptions:
- N and M are integers within the range [1..100,000];
- K is an integer within the range [1..10,000];
- each element of arrays A and B is an integer within the range [−1,000,000,000..1,000,000,000];
- array A is sorted in non-decreasing order;
- array B is sorted in non-decreasing order;
- each element of arrays P and Q is an integer within the range [0..N-1];
- each element of arrays R and S is an integer within the range [0..M-1];
- P[i] ≤ Q[i] and R[i] ≤ S[i] for 0 ≤ i < K;
- K is odd and so is Q[i]−P[i]+R[i]−S[i] for 0 ≤ i < K.
Information about upcoming challenges, solutions and lessons directly in your inbox.