It's actually similar to finding total hamming distance.
https://leetcode.com/problems/totalhammingdistance/#/description
K
kool
@kool
0
Reputation
5
Posts
73
Profile views
0
Followers
0
Following
Posts made by kool

RE: Sum of Count of Different bits

Beats 99.51% of python submission, O(n) time solution with comments.
The idea is to construct the tree from leaf node to root node rather than the other way around.
def get_ll_len(self, head): count = 0 while head is not None: head = head.next count += 1 return count def get_bst(self, n): if n <= 0: return None # recursively construct left subtree left_node = self.get_bst(n/2) # construct root node root_node = TreeNode(self.head.val) # Link above constructed left subtree with root root_node.left = left_node # progress head pointer for the linked list self.head = self.head.next """ Recursively construct the right subtree and link it with root. The number of nodes in right subtree is total nodes  nodes in left subtree  1 (for root) which is nn/21. """ root_node.right = self.get_bst(nn/21) return root_node def sortedListToBST(self, head): """ :type head: ListNode :rtype: TreeNode """ self.head = head n = self.get_ll_len(head) return self.get_bst(n)
Source: http://www.geeksforgeeks.org/sortedlinkedlisttobalancedbst/