Last Updated 2023 February 07
At some point in time, I had gotten the idea to do leetcode challenges in Ada. Ada was not a language that I knew very well. There are many things in C I can do that I can not do in Ada1, and Ada doesn’t seem to be as supported as other languages.
Sometimes, Linux distros package gnat but not
gprbuild. So I haven’t built projects in Ada. Leetcode
doesn’t support Ada for running and submitting code either. (When I
look at the list of sponsors, I can connect a few dots.) It’s no big
deal as I can do without the calendar, points, badges, and other
stuff on leetcode beyond the problem sets.
Given two sorted arrays
nums1andnums2of sizemandnrespectively, return the median of the two sorted arrays.
The overall run time complexity should be
O(log (m+n)).
(I renamed nums1 to a and
nums2 to b.)
The challenge was easy until I tried to meet the
O(log(m+n)) condition. Regardless, I implemented the
linear solution O(log(((n+m)/2)+1)) which was to merge
two lists until the middle was reached. That way I had a simple
reference for the optimal
solution.
For both functions, I don’t check for an empty
sequence (integer array) for either of the parameters
because the Ada compiler wasn’t letting me send empty arrays to
begin with (going by obvious syntax). sequence also has
a range of positive integers for indexes, so it is 1-indexed.
function partial_merge
(a: in sequence; b: in sequence; limit: in integer)
return sequence is
n : integer := a'length + b'length;
merged :sequence(1 .. limit);
i : integer := 1;
ca : integer := 1;
cb : integer := 1;
ae : integer;
be : integer;
begin
for i in 1 .. limit loop
if ca <= a'length then
ae := a(ca);
else
ae := integer'last;
end if;
if cb <= b'length then
be := b(cb);
else
be := integer'last;
end if;
if ae < be then
merged(i) := ae;
ca := ca + 1;
else
merged(i) := be;
cb := cb + 1;
end if;
end loop;
return merged;
end;
function get_median_even
(a: in sequence; b: in sequence) return float is
n : integer := a'length + b'length;
m1 : integer := n/2;
m2 : integer := (n/2)+1;
c : sequence := partial_merge(a, b, m2);
begin
put("merged: ");
print(c);
return float(c(m1)+c(m2))/2.0;
end;
function get_median_odd
(a: in sequence; b: in sequence) return float is
n : integer := a'length + b'length;
m : integer := (n/2)+1; -- index of median
c : sequence := partial_merge(a, b, m);
begin
put("merged: ");
print(c);
return float(c(m));
end;
-- first solution
function get_median
(a: in sequence; b: in sequence) return float is
n : integer := a'length + b'length;
begin
if n mod 2 = 1 then
-- if my length is 7, then i need the 4th index
return get_median_odd(a,b);
else
-- if my length is 4 then i need 2+2+1/2
-- if my length is 6 then i need 3+3+1/2
return get_median_even(a,b);
end if;
end;Meeting O(log(n+m)) requires some form of binary
search.2 The logic is easy to follow if
there was one array involved. But writing this function took more
time than I anticipated. It was the buggiest and
most often broken section of code. However, if it
gets the same answer as the other function, I consider it a pass.3
Cases covered:
a'length > 3 and b'length == 1a'length > 3 and b'length == 1 and
b'first > a'lasta'length > 3 and b'length == 1 and
b'first < a'first function get_median_optimal
(a : in sequence; b : in sequence) return float is
n : integer := a'length;
m : integer := b'length;
low : integer := 1;
high : integer := a'length;
mid_a : integer;
mid_b : integer;
left_a : integer;
right_a : integer;
left_b : integer;
right_b : integer;
answer : float;
iterations : integer := 0;
target : float := foo.log(float(m+n));
begin
if n < m then
return get_median_optimal(b, a);
end if;
while low <= high loop
mid_a := (low+high)/2; -- 6/2 = 3
mid_b := ((1+m+n)/2) - mid_a; -- 10/2 - 3 = 2
if mid_a <= 0 then
left_a := integer'first;
else -- mid_a < a'length then
left_a := a(mid_a);
end if;
if mid_a < a'length then
right_a := a(mid_a+1);
else
right_a := integer'last;
end if;
-- b is the shorter array - avoid out of bounds
if mid_b <= 0 then
left_b := integer'first;
elsif mid_b < b'length then
left_b := b(mid_b);
elsif mid_b >= b'length then
left_b := b(b'last);
end if;
if mid_b < 0 then
right_b := b(b'first);
elsif mid_b < b'length then
right_b := b(mid_b+1);
else
right_b := integer'last;
end if;
-- both left values are less than both right values
if (left_a <= right_b)
and (left_b <= right_a) then
if ((n + m) mod 2) = 0 then
answer := float(
integer'max(left_a, left_b)
+ integer'min(right_a, right_b)
) / 2.0;
exit;
else
answer := float(integer'max(left_a, left_b));
exit;
end if;
elsif (left_a > right_b) then
high := mid_a - 1;
elsif (left_b > right_a) then
low := mid_a + 1;
end if;
iterations := iterations +1;
end loop;
put("iterations: " & iterations'image);
put("; target: O(ln(m+n)) = " & target'image);
if float(iterations) <= target then
put(" ✓");
end if;
new_line;
return answer;
end;----------------------
a = 1 3
b = 2
merged: 1 2
iterations: 0; target: O(ln(m+n)) = 1.09861E+00 ✓
median = 2.0
test case # 1 passed
----------------------
a = 1 2
b = 3 4
merged: 1 2 3
iterations: 1; target: O(ln(m+n)) = 1.38629E+00 ✓
median = 2.5
test case # 2 passed
----------------------
a = 1 2 3 4 10
b = 5 6 11
merged: 1 2 3 4 5
iterations: 1; target: O(ln(m+n)) = 2.07944E+00 ✓
median = 4.5
test case # 3 passed
----------------------
a = 1 2 3 4 10 12 13 14 15 16 20 27 30
b = 5 6 11
merged: 1 2 3 4 5 6 10 11 12
iterations: 2; target: O(ln(m+n)) = 2.77259E+00 ✓
median = 11.5
test case # 4 passed
----------------------