Problem Statement

Compute factorial of a given number n, where n >= 0.

Problem Domain Analysis

Factorial is defined as follows:

n! = 1 x 2 x 3 x ... n for n >= 1

Given that 0! = 1 Solution Domain Analysis We observe a pattern, so we can rewrite 4! as :

4! = 3! x 4

if n = 4,

n! = (n-1)! x n We can rewrite the examples as :

Step 1 : 0! = 1
Step 2 : 1! = 1 x 0!
Step 3 : 2! = 2 x 1!
Step 4 : 3! = 3 x 2!
Step 5 : 4! = 4 x 3!

You can make these examples executable. Numbers cannot be negative. If the contract is broken you raise an exception. This problem lends itself to writing specs directly from the examples. We did not have to come up with a well ordered sequence of test cases before we start writing the tests.

Algorithm

1. Take the input number n
2. Treat 0! as a special case while less than n products has been calculated, repeatedly do
a) Increment index count
b) Compute the product for current index by multiplying index by the current product
end

Return the result

Steps

Step 1

In our case the class name will be Factorial. Create a file called factorial_spec.rb with the following contents:

describe Factorial do

it '0 factorial is 1' do
factorial = Factorial.new(0)

result = factorial.calculate

expect(result).to eq(1)
end

end

The describe() is a rspec method. It takes a class name in this case, Factorial as the parameter.

Step 2

Run the spec.

\$rspec factorial_spec.rb

Step 3

Define an empty Factorial class at the top of the factorial_spec.rb as follows:

class Factorial

end

Step 4

When you run the spec, you will get error related to constructor argument. Change the Factorial class as follows:

class Factorial
def initialize(n)
@n = n
end
end

Step 5

Now you get an error due to undefined method 'calculate'. Let's define the method now as follows:

class Factorial
def initialize(n)
@n = n
end

def calculate

end
end

Step 6

You see an error 'expected 1 got nil'. We are now failing for the right reason.

Step 7

Return a hardcoded 1 from the calculate method.

class Factorial
def initialize(n)
@n = n
end

def calculate
1
end
end

Now we are green.

Discussion

We went from no code at all (missing calculate method) to code that returns nil. This is the very first transformation in the Transformation Priority Premise transformations list. Then we went from nil to constant. This is the second transformation from TPP transformations list. We also discovered the public API for the Factorial class.

Step 8

Let's write a executable spec for the second example that we came up with in the solution domain analysis section. Add the second spec as follows:

describe Factorial do
# first test same as before
it '1 factorial is 1' do
factorial = Factorial.new(1)

result = factorial.calculate

expect(result).to eq(1)
end
end

The test passes. It's obvious why, we still have fake implementation that returns 1.

Step 9

Let's add the third spec as follows:

describe Factorial do
# first two tests same as before
it '2 factorial is 2' do
factorial = Factorial.new(2)

result = factorial.calculate

expect(result).to eq(2)
end
end

This fails with expected 2 got 1 error.

Step 10

How can we make the new spec pass without making the old ones fail? Change the implementation as follows:

def calculate
if @n == 0
1
else
@n
end
end

All specs pass.

Discussion

We transformed our code from no conditional to splitting the execution path by using if-else construct. This transformation is somewhere in the middle of the TPP transformations list.

Step 11

Let's add the next spec as follows:

describe Factorial do
# first three tests same as before
it '3 factorial is 6' do
factorial = Factorial.new(3)

result = factorial.calculate

expect(result).to eq(6)
end
end

The test fails with the error 'expected 6 got 3' message.

Step 12

Solution 1 : We can use recursion and use the formula we came up with by recognizing the pattern. Formula for recursive solution:

n! = (n-1)! x n

Solution 2 : We can use our algorithm we developed earlier:

while less than n products has been calculated, repeatedly do
a) Increment index count
b) Compute the product for current index by multiplying index by the current product
end

return the result

The terminating condition is that we reach 1 as we reduce the number by 1 inside the loop. The initial value of the result is set to 1. Here is the pseudocode:

result = 1
while n > 1 do
result = result * n
n = n - 1
end

Change the implementation as follows:

class Factorial
def initialize(n)
@n = n
end

def calculate
if @n == 0
1
else
result = 1
while @n > 1 do
result = result * @n
@n = @n - 1
end
result
end
end
end

All specs pass.

Step 13

Let's cleanup the code as follows:

class Factorial
def initialize(n)
@n = n
end

def calculate
result = 1
while @n > 1 do
result = result * @n
@n = @n - 1
end
result
end
end

Discussion

You can now see that the if-else became a while construct. This is in the bottom of the TPP transformations list. While is much more generic construct than if-else. We no longer need a special case to handle the 0!. The boundary case is handled by the initial condition. If you observe the changes that happened in the above steps, you can see how Robert Martin's insight 'As the tests get more and more specific, the code gets more and more generic' is true in our case.

Exercises

1. Change the implementation to use recursive solution. Make sure all tests pass. Watch out for the common mistake of forgetting terminating condition for recursive solution.
2. Watch the Factorial screencast or download Factorial screencast
3. Write the following contract test.
it 'should raise exception for negative numbers'

You can implement it by using the following code:

raise ArgumentError, 'Negative number is not allowed' if number < 0

Ace the Technical Interview

• Easily find the gaps in your knowledge
• Get customized lessons based on where you are
• Take consistent action everyday
• Builtin accountability to keep you on track
• You will solve bigger problems over time
• Get the job of your dreams

Take the 30 Day Coding Skills Challenge

Gain confidence to attend the interview

No spam ever. Unsubscribe anytime.