Add Two Numbers Without the Addition Sign (Ruby)

A weird interview question for software development interviews is “add these two numbers without using the plus sign.” I was taken aback by how zen-like and strange this question sounds at first, but by using a bit of binary math I was able to solve it.

My First Approach

Example input: Add 5 and 8

In ruby, the to_s method can turn Fixnums into their binary form.

I’m going to add a “0” to the start of the binary representation of five so it’s the same length as the eight.

Adding 5 to 8 is a special case because there is no instance where you have to carry the one. My naive first approach was to use the | (or) operation on each digit and you will get the desired result.

0101 | 1010 => 1101

Because,

0 | 1 => 1

0 | 0 => 0

1 | 0 => 1

0 | 1 => 1

So our answer is “1101”, which is equal to our goal, 13. (1 + 4 + 8)

However, this will not work with something like 4 + 4. The binary form of 4 is “100” and 8 is “1000”. Trying the naive approach above,

100 | 100

0 | 0 => 0

0 | 0 => 0

1 | 1 => 1

100 + 100 = 100? Something went wrong. So, we need to literally “carry the one” when both digits equal 1

0 ? 0 => 0

1 ? 0 => 1

1 ? 1 => 10

0 ? 1 => 1

It took me quite a bit of trial and error to tackle this problem, but here is my solution.

The Plan

(1) Helper function to go from a decimal number to a binary number array, e.g., 5 -> [1, 0, 1]

(2) Helper function to add zeros to the front of the shorter array to equalize the length of two binary arrays, e.g.,

[1, 0, 1] and [1, 0, 0, 0] become

[0, 1, 0, 1]  and [1, 0, 0, 0]

(3) Function to add bits, e.g., 0 & 0, 1 & 0, and also take into account ‘carrying’ bits over.

(4) Function to add the entire binary array

(5) Function to convert back from binary array to decimal

(6) Function that puts it all together! Input two decimal numbers and output their sum.

The Ruby Program 

(1) Decimal to binary array

#input: decimal e.g. 5
#output: binary array e.g. [1,0,1]
def dec_to_bin_array(dec_num)
  #turn into array of string chars
  bin = dec_num.to_s(2).chars
  #convert to integers
  bin.map(&:to_i)
end

(2) Equalize length of two binary arrays

#input: two arrays of 0s and 1s
#insert leading zeros to beginning of shorter array to equalize length
def equalize_length(arr1, arr2)
  while arr1.length < arr2.length
    arr1.unshift(0)
  end
  while arr2.length < arr1.length
    arr2.unshift(0)
  end
end

(3) Add bits together and take into account carry operations

#input: bit1, bit2, amount to carry
#output: [digit to carry over, digit to insert to end of sum]
def add_bits(bit1, bit2, carry)
  return [1, 1] if bit1 == 1 && bit2 == 1 && carry == 1
  return [1, 0] if (bit1 == 1 || bit2 == 1) && carry == 1
  return [0, 1] if (bit1 == 0 && bit2 == 0) && carry == 1
  return [1, 0] if bit1 == 1 && bit2 == 1 && carry == 0
  return [0, 1] if (bit1 == 1 || bit2 == 1) && carry == 0
  [0, 0]
end

(4)  Add each bit of the arrays together to form the bit sum

def add_binary_arrays(arr1, arr2)
  sum = []
  equalize_length(arr1, arr2)
  carry_digit = 0
  while !arr1.empty?
    m = arr1.pop
    n = arr2.pop
    v = add_bits(m, n, carry_digit)
    carry_digit = v[0]
    sum.unshift(v[1])
  end
  sum.unshift(carry_digit)
  sum
end

(5) Go from binary array to decimal (recursive approach)

def bin_array_to_dec10(arr, n = 0, pow = 0)
  return n if arr.empty?
  n += arr.pop * (2**pow)
  bin_array_to_dec10(arr, n, pow + 1)
end

(6) Put all the above together to get the answer.

#input: two base10 numbers
#output: their sum 🙂
def add_two_numbers_using_bitwise_operations(a, b)
  m = dec_to_bin_array(a)
  n = dec_to_bin_array(b)
  v = add_binary_arrays(m, n)
  bin_array_to_dec10(v)
end

I found this problem enjoyable to work through because it helped me understand one of the most fundamental operations performed by the computer.

Mental Exercise for Menial Chores

If there’s one thing I learned from teaching, it’s that one of the most mind numbing activities is test proctoring. Most proctors aren’t allowed to use their smartphone, read a book, draw, or even sit. You are supposed to walk around and “actively proctor,” whatever that means. One of my coping tricks was to determine the collatz sequence of a random starting number, mentally.

A collatz sequence is a simple algorithm that creates a chain of numbers based on a starting ‘seed’ number. The rule is simple:

If n is even then:

n –> n/2

If n is odd then:

n –> 3n + 1

For example if you start with 5, an odd number, the next number would be

3*5 + 1 = 16

Since 16 is even, we divide it by two, so the next number is 8. So far our sequence is

5 –> 16 –> 8

Since 8 is even, we divide by two again, giving us 4. Divide that, and on and on until you reach 1. The overall sequence contains 6 numbers:

5 — > 16 –> 8 –> 4 –> 2 –> 1

This is called the collatz conjecture because it’s unproven whether or not any starting number will always reach one, like in the example above. Here is the question from Project Euler  which I will try to solve.

Which starting number, under one million, produces the longest chain?

How I will approach this problem

  1. Write a helper function that will determine the next number in the sequence
  2. Write a function that will loop through every number keeping track of the number of iterations.
  3. Once the chain has finished, check if it has surpassed the last winner. If it has, then replace it as the current ‘leader’ .

First, the helper function to determine the next number:

def next_collatz(n)
  if (n%2 == 0)
    return n/2
  else
    return 3*n+1
  end
end

Then, declare the variables to keep track of the current leader (longest)

longest = 0
counter = 1
winning_num = 0
x = 1

Construct the loop to go through all numbers less than one million

while counter < 1000000
  x = counter
  chain = 1
  while x > 1
    x = next_collatz(x)
    chain+=1
  end
  #print("N: ", counter, " Had a chain of: ",chain,"\n")
  if (chain > longest)
    longest = chain
    winning_num=counter
  end
  counter+=1
end

Print the winner!

print("longest: ",longest," winningnum: ",winning_num,"\n") #Note this is the number that produces the longest chain, not the length of chain

 

Champernownes Constant

Champernowne was a mathematician/friend of Alan Turing who is most well known for his research on his self-named number, Champernowne’s Constant. You can generate this number by appending positive integers in ascending order after the decimal place:

0.123456789101112131415… etc.

It was a lot easier to come up with unique numbers in the 30’s.

Here are the challenges

1. Write an algorithm to quickly determine what number (0-9) is at a given index. For example, c(4) = 4, c(11) = 0, c(14) = 1, etc.

2. From Project Euler: Determine the product of c(1) * c(10) * c(100) * c(1,000) * c(10,000) * c(100,000) * c(1,000,000)

Since this number is a geometric series, you must know the previous number to generate the next. There is a tempting brute force approach:

c = "0."
i = 1
while i < 10000000
  c += i.to_s
  i += 1
end

While that does work, after 100,000 loops you’re going to start running out of memory. Here’s a better, but still nonfunctional solution:

idxs = [1, 10, 100, 1000, 10000, 100000, 1000000]
i = 1 #loop number counter
prod = 1
index = 1
c = "0"
while i <= 1000000
  s = i.to_s #we need to check each digit in the string
  #p s
  #c += s
  s.chars.each_index do |j|
    if idxs.include?(index)
      prod *= s[j].to_i
    end
    index += 1 #this is the current place in the constant
  end
  i+=1
end
p prod

That works by changing a second incrementor, index, based on each number’s value. For example, the number ’12’ would change index by 2, the number ‘142’ would change index by 3, etc. It is still too slow to actually do the math.

Unable to find a solution fast enough to store the value in memory and look through it, I went with storing the data into a file instead, and reading in from the file.

First we create the file:

#Approximately 6mb
File.open("champernownes", "a") do |f|
  i = 0
  while i < 1000000
    f<<i.to_s
    i+=1
  end
end

Then we read through it character by character, storing the product whenever we reach one of the indices relevant to the challenge.

idxs = [1, 10, 100, 1000, 10000, 100000, 1000000]
prod = 1
File.open("champernownes", "r") do |f|
  i = 0
  f.each_char do |c|
    if idxs.include?(i)
      prod *= c.to_i
    end
    i+=1
  end
end
p prod

Be assured this is nowhere near the fastest algorithm for solving this problem, but it was one of the first times that I considered storing the ‘brute force’ solution into a file and then reading from that.