This notebook was prepared by Donne Martin. Source and license info is on GitHub.

Solution Notebook

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]:
class Solution(object):

    def calc_utopian_tree_height(self, 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
import unittest


class TestUtopianTree(unittest.TestCase):

    def test_utopian_tree(self):
        solution = Solution()
        self.assertEqual(solution.calc_utopian_tree_height(0), 1)
        self.assertEqual(solution.calc_utopian_tree_height(1), 2)
        self.assertEqual(solution.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