We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Implementation
  4. Utopian Tree
  5. Discussions

Utopian Tree

  • lopezredd
     + 0 comments

    Here's my solutions in python:

    Tested when n = 1000

    Solution 1: Average(961 ns)

    def utpoianTree(n):
	return int(2**((n / 2) + 1) - 1 if n % 2 == 0 else 2**(((n + 1) / 2) + 1) - 2)

    Solution 2: Average(138 µs):

    def utopianTree(n):
    height = 1
    for p in range(1, n+1):
        if p % 2 == 0:
            height += 1
        else:
            height *= 2

    return height

    Solution 3: More readable version of the first solution Average(1.47 µs):

    def utopianTree(n):
    is_even = n % 2 == 0
    # adjust n so is divisible by 2
    adusted_n = n if is_even else n + 1
    # truncate float value from division -> parse to int
    half_cycles = (adusted_n / 2).__trunc__() + 1
    growth_factor = 2**half_cycles

    if is_even:
        return growth_factor - 1

    return growth_factor - 2