pv
BAN USERIn order successor in a BST will be the smallest number greater than the given number.
Which would be the left most node in its right subtree.
def in_order_successor(node):
if node.right is None:
return None
temp_node = node.right
while temp_node.left != None:
temp_node = temp_node.left
return temp_node
For the given sample input, the permutation suggested by ArunKumar, {5, -1, 5, 3}, gives 6 + |-6 + 2| = 10 but the permutation {5, 3, -1, 5} gives 2 + |4 + 6| = 12.
Am I missing something here?
Since the input is guaranteed to be of length 4 at all times, why is the brute force 4! recursive approach wrong? It's still O(1) time and space.
Ticket from one city to the other is an edge.
Given a bunch of edges, the question asks you to tell if there exists a path such that you visit each edge exactly once.
In other words, a Eulerian Path.
Below is the necessary and sufficient condition for a Eulerian path in directed graphs. (Source: Wikipedia)
A directed graph has an Eulerian trail if and only if at most one vertex has (out-degree) − (in-degree) = 1, at most one vertex has (in-degree) − (out-degree) = 1, every other vertex has equal in-degree and out-degree, and all of its vertices with nonzero degree belong to a single connected component of the underlying undirected graph.
This however is a necessary condition but not sufficient.
Existence of a Eulerian path can actually be deduced from common sense. If you haven't left every city you have been to except for the one you are currently in, you wouldn't end up where you are.
But we are looking for one and only one Eulerian path to exist, which is possible only if every vertex has an indegree and outdegree of at most 2.
Assume the loop has 'n' nodes.
- pv November 28, 2013Let the node in the loop that runner first lands at be 'N'.
After 'i' iterations, runner would be 2*i % n nodes away from N.
Assume the follower arrived at N, 'k' iterations behind the runner.
After 'i' iterations (we are interested only in i >= k), follower would be (i - k) % n nodes away from N.
The question is now reduced to proving that for any 'k' there exists an integer 'i' such that,
2*i % n = (i - k) % n
=> 2i = i - k + cn (where c is any integer)
=> i + k = cn
Since we are interested in only non-negative 'k' and i > k,
i = cn - k, where c is any integer > k/n