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.
This problem can be framed as special kind graph coloring problem. The vertices are inputs of truth table. We omit input values to 2 truth tables that are the same. Input values to truth table are the outputs of function F and G. Problem can be solved using recursion. For a given vertex we have 2 choices. We mark as 0 or 1. In the first case case we mark the vertex as visited and not count it. In the second case we mark the vertex and all its neigbours as visited and they are not included in the next count. Often the graph can be split into separate components. For them total count is just the product aff all counts of all components. There are 2 base cases. We have a graph wwith all marked vertices - count is 1 then or we have graph with one vertex which can have 0 or 1 valu, that is count is 2.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #209: Circular Logic
You are viewing a single comment's thread. Return to all comments →
This problem can be framed as special kind graph coloring problem. The vertices are inputs of truth table. We omit input values to 2 truth tables that are the same. Input values to truth table are the outputs of function F and G. Problem can be solved using recursion. For a given vertex we have 2 choices. We mark as 0 or 1. In the first case case we mark the vertex as visited and not count it. In the second case we mark the vertex and all its neigbours as visited and they are not included in the next count. Often the graph can be split into separate components. For them total count is just the product aff all counts of all components. There are 2 base cases. We have a graph wwith all marked vertices - count is 1 then or we have graph with one vertex which can have 0 or 1 valu, that is count is 2.