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

# Solution Notebook¶

## Problem: Utopian Tree¶

See the HackerRank problem page.

## 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