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.
Solved this problem in O(T log T). For those seeking hints: one can look at this problem as being a graph problem, in which each letter is a Node and "letter X has to occur before letter Y in the passcode" is a directed edge from X to Y. You can then repeatedly take the lexicographically smallest letter with in-degree zero (this will be the next letter in the passcode) and remove it from the graph. If there is no letter with in-degree zero, then something is wrong.
By using the right data structures, you can do this in O(E log E) where E is the number of edges in the graph.
Let me know if you solved this problem in a completely different way, I'm curious!
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #79: Passcode derivation
You are viewing a single comment's thread. Return to all comments →
Solved this problem in O(T log T). For those seeking hints: one can look at this problem as being a graph problem, in which each letter is a Node and "letter X has to occur before letter Y in the passcode" is a directed edge from X to Y. You can then repeatedly take the lexicographically smallest letter with in-degree zero (this will be the next letter in the passcode) and remove it from the graph. If there is no letter with in-degree zero, then something is wrong. By using the right data structures, you can do this in O(E log E) where E is the number of edges in the graph.
Let me know if you solved this problem in a completely different way, I'm curious!