Add two numbers using lists

Learning
1

I am writing code to find the sum of two numbers, each represented by list whose nodes contain decimal digits in reverse order. E.g., sum [2; 4; 3] [5; 6; 4] = [7; 0; 8] since 342 + 465 = 807.

Now, if the digits were stored in non-reverse order, then the following would work in O(n) time:

let sum l1 l2 =
  let rec loop carry result l1 l2 =
    match l1, l2 with
    | [], [] -> result
    | [], h::t
    | h::t, [] ->
      let sum = h + carry in
      let carry = sum / 10 in
      loop carry ((sum mod 10)::result) [] t
    | h1::t1, h2::t2 ->
      let sum = h1 + h2 + carry in
      let carry = sum / 10 in
      loop carry ((sum mod 10)::result) t1 t2
  in
  loop 0 [] l1 l2

If I were to change (sum mod 10)::result to result @ [sum mod 10] to get the result in reverse order, then the asymptotic running time would be O(n^2), due to the asymptotically linear time of the append operation.

In imperative languages, the pointer to the next element could be saved, removing the need to walk the list with each append operation.

I am new to OCaml and am wondering if there is a way I can write this in O(n) time.

2

Well, the most naive (but straightforward) way to achieve linear time is to just List.rev the final result. O(2n) is still O(n).

3 Likes
3

Since you brought up imperative languages, so I assume imperative/mutable data structures are acceptable.

In that case, you can always swap to Array.

But as mentioned above, List.rev still gives you O(n), so doesn’t really matter if it’s for exercise.