aishraj

The number of 1's in the range 0..X (X is positive) is easy to calculate (Can you get a simple recurrence which does this in O(log X) ?) Another observation is that the number of 1's in -X is equal to the number of 0's in ~(-X) = X - 1. Using this, it is easy to calculate the answer for negative ranges as well.

aishraj

The answer is the number of inversions in the array, which is the number of pairs i,j such that i < j and a[i] > a[j]. Counting this is a fairly classical problem with many solutions such as using data structures such as Balanced Trees or Binary Indexed Trees. Another particularly elegant solution involves modifying merge sort to count the number of inversions when merging the two sorted halves in the algorithm.

aishraj

The line graph of a graph G is a graph having the edges of G as it's nodes and edges between them if the corresponding edges in G are adjacent. The Hamiltonian Completion Number is the minimum number of edges to be added to a graph for it to have a Hamiltonian Cycle.

Formally, the problem can be stated as asking for the Hamiltonian Completion Number of the line graph of a tree. While this problem is NP-Complete for the general case, it is in fact solvable in polynomial (linear actually) time for trees. Again, I do not have a simple algorithm, or a proof of why the algorithm works. Feel free to look at solutions or read up more about the problem online. See: http://en.wikipedia.org/wiki/Hamiltonian_completion http://www.sciencedirect.com/science/article/pii/S0020019000001642

Note that the caterpiller trees discussed above are precisely the trees for which the Hamiltonian Completion Number of their line graphs is 0.

aishraj

Such a tour exists only when the tree is a caterpiller tree which is a tree consisting of a straight path with some leafs attached to nodes on that path. Using this observation, getting a recurrence and solving it using Dynamic Programming is greatly simplified. Also, working out some examples on paper, it is easy to see that the answer is 2 * n1! * ... * nk! where n1,..,nk are the number of leafs attached to each node on the path defining the caterpiller tree. A special case is when the tree is a star, when the answer is simply (n - 1)!. See: http://en.wikipedia.org/wiki/Caterpillar_tree

aishraj

The answer is the number of inversions in the array, which is the number of pairs i,j such that i < j and a[i] > a[j]. Counting this is a fairly classical problem with many solutions such as using data structures such as Balanced Trees or Binary Indexed Trees. Another particularly elegant solution involves modifying merge sort to count the number of inversions when merging the two sorted halves in the algorithm.

aishraj

The main observation is that the card at index i (1 <= i <= N) ends up at index K * i % (N + 1) after 1 shuffle. So after x shuffles, the card will be at position K^x * i % (N + 1). We want to find the smallest x such that K^x * i = i for all i. In other words, we want K^x = 1. This is known as the multiplicative order of K mod (N + 1). Lagrange's theorem implies that this will be a factor of phi(N + 1) where phi is the Euler Totient function. So we can check all factors of phi(N + 1) and find the smallest one which works. See: http://en.wikipedia.org/wiki/Euler's_totient_function http://en.wikipedia.org/wiki/Lagrange's_theorem_(group_theory)

aishraj

Queens on a Board Solution (InterviewStreet CodeSprint Fall 2011)

aishraj

Such a tour exists only when the tree is a caterpiller tree which is a tree consisting of a straight path with some leafs attached to nodes on that path. Using this observation, getting a recurrence and solving it using Dynamic Programming is greatly simplified. Also, working out some examples on paper, it is easy to see that the answer is 2 * n1! * ... * nk! where n1,..,nk are the number of leafs attached to each node on the path defining the caterpiller tree. A special case is when the tree is a star, when the answer is simply (n - 1)!. See: http://en.wikipedia.org/wiki/Caterpillar_tree

aishraj

Considering each permutation of the letters as a variable, we get a number of simultaneous equations which can be solved using Gaussian Elimination to compute the expected value of each permutation. However, the number of variables is very large. This can be reduced by making the observation that many states such as "abab" and "baba" are essentially the same since the letters in them are simply relabelled. Thus we can normalize each string by letting it start with an 'a', replacing the next occuring character with a 'b' and so on. For example, string "paddpa" would be normalized to "abccab". This reduces the number of variables greatly, and also helps us efficiently memoize across various test cases. Also, we should note that running one Gaussian Elimination gives us the expected values for many states (and not just one), all of which should be saved for future reference.

aishraj

The answer is the number of inversions in the array, which is the number of pairs i,j such that i < j and a[i] > a[j]. Counting this is a fairly classical problem with many solutions such as using data structures such as Balanced Trees or Binary Indexed Trees. Another particularly elegant solution involves modifying merge sort to count the number of inversions when merging the two sorted halves in the algorithm.