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.
Iterative solution. The first lexigraphic solution is always x 'H's followed by y 'V's. If we consider when the leftmost V moves left, for y = 2 it's 1,3,6,10,15...,
for y=3 it's 1,4,10,20,35... In general it's the yth figurate number. Figurate numbers are choose(n+y - 1, y) so the reason for this should be apparent (the leftmost V moves after all combinations to its right are exhausted).
The V's to the right follow the same pattern, repeated every time the V to the left moves.
So, solution is find maximum yth figurate number less than k. The index of this number tells us where the leftmost V is. Subtract that from k. Then find maximum y-1st figurate number less than the remainder, and so on.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Lexicographic paths
You are viewing a single comment's thread. Return to all comments →
Iterative solution. The first lexigraphic solution is always x 'H's followed by y 'V's. If we consider when the leftmost V moves left, for y = 2 it's 1,3,6,10,15..., for y=3 it's 1,4,10,20,35... In general it's the yth figurate number. Figurate numbers are choose(n+y - 1, y) so the reason for this should be apparent (the leftmost V moves after all combinations to its right are exhausted).
The V's to the right follow the same pattern, repeated every time the V to the left moves.
So, solution is find maximum yth figurate number less than k. The index of this number tells us where the leftmost V is. Subtract that from k. Then find maximum y-1st figurate number less than the remainder, and so on.