This notebook was prepared by [Donne Martin](http://donnemartin.com). Source and license info is on [GitHub](https://github.com/donnemartin/interactive-coding-challenges).

Solution Notebook

Problem: Utopian Tree

See the HackerRank problem page.

Constraints
Test Cases
Algorithm
Code
Unit Test

Constraints

See the HackerRank problem page.

Test Cases

See the HackerRank problem page.

Algorithm

If cycles is 0, return height of 1
For 1 to cycles:
- If cycle is odd, double height
- Else, increment height
Return height

Complexity:

Time: O(n)
Space: O(1)

Code



In [1]:

    
def calc_utopian_tree_height(cycles):
    height = 1
    if cycles == 0:
        return height
    for i in range(1, cycles+1):
        if i % 2 == 1:
            height *= 2
        else:
            height += 1
    return height

Unit Test



In [2]:

    
%%writefile test_utopian_tree.py
from nose.tools import assert_equal


class TestUtopianTree(object):

    def test_utopian_tree(self):
        assert_equal(calc_utopian_tree_height(0), 1)
        assert_equal(calc_utopian_tree_height(1), 2)
        assert_equal(calc_utopian_tree_height(4), 7)
        print('Success: test_utopian_tree')


def main():
    test = TestUtopianTree()
    test.test_utopian_tree()


if __name__ == '__main__':
    main()









    



Overwriting test_utopian_tree.py



In [3]:

    
run -i test_utopian_tree.py









    



Success: test_utopian_tree