5
\$\begingroup\$

I am solving the following problem:

You are given two lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a list.

I wrote the following code:

let addTwoNumbers (a: int list) (b: int list) =
    let rec loop (a: int list) (b: int list) (c: int list) (carry: int) =
        match a, b, carry with
        | (h1::t1), (h2::t2), _ ->
            let q, r = Math.DivRem(h1 + h2 + carry, 10)
            loop t1 t2 (List.append c [r]) q
        | (h1::t1), [], _ ->
            let q, r = Math.DivRem(h1 + carry, 10)
            loop t1 [] (List.append c [r]) q
        | [], (h2::t2), _ ->
            let q, r = Math.DivRem(h2 + carry, 10)
            loop [] t2 (List.append c [r]) q
        | [], [], 0 ->
            c
        | [], [], carry ->
            let q, r = Math.DivRem(carry, 10)
            loop [] [] (List.append c [r]) q
    loop a b [] 0

Is there a way to simplify and possibly to de-duplicate some of this code?

\$\endgroup\$
  • \$\begingroup\$ Here's one way to split and concatenate digits into numbers, and the other way around: stackoverflow.com/a/31637121/126014 \$\endgroup\$ – Mark Seemann Aug 8 '15 at 14:18
  • \$\begingroup\$ If this is a programming challenge, please consider adding the "programming challenge" tag and the source of the exercise if possible. \$\endgroup\$ – morbidCode Aug 8 '15 at 14:25
2
\$\begingroup\$

List.append is an expensive O(d) operation, making your addTwoNumbers O(d2). To reverse the list, you would be better off calling List.rev once at the end. (By the way, List.append c [r] would be better written as c @ [r].)

The loop helper function could use a better name. My suggestions are either add or addTwoNumbers'. I don't like the name c either, as it is somewhat mnemonically similar to carry.

Put the base cases first, followed by the recursive cases.

One of the cases can be simplified by taking advantage of commutativity.

When adding two numbers, carry should never be greater than 1.

let addTwoNumbers (a: int list) (b: int list) =
    let rec add (a: int list) (b: int list) (sum: int list) (carry: int) =
        match a, b, carry with
        | [], [], 0 ->
            sum
        | [], [], 1 ->
            1 :: sum
        | [], _, _ ->
            add b a sum carry
        | (h1::t1), [], _ ->
            let c, s = Math.DivRem(h1 + carry, 10)
            add t1 [] (s :: sum) c
        | (h1::t1), (h2::t2), _ ->
            let c, s = Math.DivRem(h1 + h2 + carry, 10)
            add t1 t2 (s :: sum) c
    add a b [] 0 |> List.rev
\$\endgroup\$
0
\$\begingroup\$

If your inputs can be adjusted to the same length, prior to calling the function, you can leverage Zip and Fold and simplify the algorithm. (Instead of writing a recursive function and using pattern matching on 5 patterns.)

let addTwoNumbers digits1 digits2 = 

    let carryLast, answer = 
        Seq.zip digits1 digits2
        |>  Seq.fold
                (fun (carry, result) (v1, v2) -> 
                    let div, rem = Math.DivRem ( carry + v1 + v2 , 10)
                    (div, rem :: result)) 
                (0, [])

    if carryLast = 0
        then answer
        else carryLast :: answer
\$\endgroup\$

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.