Road to Genius: superior #65

Each day I solve several coding challenges and puzzles from Codr's ranked mode. The goal is to reach genius rank, along the way I explain how I solve them. You do not need any programming background to get started, and you will learn a ton of new and interesting things as you go.

function Node(val) {
    this.val = val;
    this.next = null;
}

function myst(cur1, cur2) {
  if (cur1 === null || cur2 === null)
    return null;
  let head = new Node(0)
  let cur = head 
  let carry = 0 
  while (cur1 !== null || cur2 !== null) {
    let val1 = cur1 !== null ? cur1.val : 0
    let val2 = cur2 !== null ? cur2.val : 0
    let sum = val1 + val2 + carry
    let newNode = new Node(sum % 10) 
    carry = sum >= 10 ? 1 : 0 
    cur.next = newNode
    cur = cur.next
    if (cur1 !== null)
      cur1 = cur1.next
    if (cur2 !== null)
      cur2 = cur2.next
  }
  if (carry > 0)
    cur.next = new Node(carry)
  return head.next
};

let x = new Node(9)
x.next = new Node(6)
x.next.next = new Node(1)

let y = new Node(7)
y.next = new Node(8)
y.next.next = new Node(1)

let out = myst(x, y);
let A = out.val;
while (out.next) {
  A += out.val;
  out = out.next
}

// A = ? (number)

Here's a challenge we haven't encountered before. It seems to be related to linked lists, if you're new to programming this is an important data structure to learn.

This code creates two separate linked lists x and y (at the end of the code). Then some mysterious function myst is called using x and y as arguments. Finally variable A is being computed depending on the output of myst.

A linked lists' basic structure is a Node. A simple node contains some value and a pointer to the next node. A linked list is simply a chain of nodes:

Now that you understand linked lists, let's analyze the function myst. It's taking two linked lists, and iterates both of them from head to tail. It creates a new linked list head whose nodes' values are computed by sum:

    let sum = val1 + val2 + carry
    let newNode = new Node(sum % 10) 
    carry = sum >= 10 ? 1 : 0 

Let's illustrate this whole process in pseudo-code:

x => (9) -> (6) -> (1) -> END
y => (7) -> (8) -> (1) -> END

myst(x, y)
  head => (0) -> END  
  carry = 0
  while :
    sum = (9 + 7 + 0) % 10 = 6
    newNode => (6) -> END
    carry = 1
    head => (0) -> (6) -> END

    sum = (6 + 8 + 1) % 10 = 5
    newNode => (5) -> END
    carry = 1
    head => (0) -> (6) -> (5) -> END

    sum = (1 + 1 + 1) % 10 = 3
    newNode => (6) -> END
    carry = 0
    head => (0) -> (6) -> (5) -> (3) -> END

  return head.next


out => (6) -> (5) -> (3) -> END
A = 6
while:
  A += 6
  A += 5
  //// A += 3 is not done because that node's "next" points to END (null)
A == 17

By solving these challenges you train yourself to be a better programmer. You'll learn newer and better ways of analyzing, debugging and improving code. As a result you'll be more productive and valuable in business. Get started and become a certified Codr today at https://nevolin.be/codr/