Another Casual Coder

Saw this problem on a Facebook post today: To write a code for it, we can use DFS + backtracking. We can actually make it general enough so that we can solve it for: 1/ Any set of digits 2/ Broken into any group of numbers 3/ Looking for any target The result for the puzzle above is this:  225 189 112 Code probably needs more boundary checks (overflows) as well as pruning of the search space, but for the most part it works. Code is down below, cheers, ACC. using System; using System.Collections; using System.Collections.Generic; using System.Numerics; namespace ProductNumbersTarget { class Program { static void Main(string[] args) { int[] digits = { 9, 2, 5, 2, 1, 1, 8, 2, 1 }; Array.Sort(digits); BigInteger[] numbers = new BigInteger[3]; for (int i = 0; i < numbers.Length; i++) numbers[i] = 0; BigInteger target = 4762800; FindProductArrangement(digits, new Hashtable(), numbers, 0, targ

Robert Floyd and Stephen Warshall (in the pictures below, from Wikipedia) died relatively young for today's standards. It was a pity as I believe they would have had at least another strong productive 20 years ahead of them. But they left us a great legacy, one of them int the Floyd–Warshall Algorithm. This algorithm manages to calculate the distance between any two nodes (a,b) in a graph in O(n^3), which is unbelievably fast. Notice that it does beat Dijkstra since this one only allows you to find the min distance between a node and all the other ones, whereas Floyd-Warshall gives you a nice nxn table with all the distances. It is a variation of Dynamic Programming. This problem below requires the use of Floyd–Warshall Algorithm. Once you have the table with the min distance across all the nodes (and remember since n=10^2, the algorithm will run in 10^6, very tractable), then a simple n^2 parse is required to find the solution. Code is down below, cheers, ACC. Find the City With t

Problem is actually not that hard, as long as you don't have any qualms in using some extra space: 1/ Flatten the list to a List<int>. Simple DFS (remember that N=10^3) 2/ Create the final list from the List<int> Code is down below, cheers, ACC. Flatten a Multilevel Doubly Linked List - LeetCode 430. Flatten a Multilevel Doubly Linked List Medium 3262 242 Add to List Share You are given a doubly linked list, which contains nodes that have a next pointer, a previous pointer, and an additional  child pointer . This child pointer may or may not point to a separate doubly linked list, also containing these special nodes. These child lists may have one or more children of their own, and so on, to produce a  multilevel data structure  as shown in the example below. Given the  head  of the first level of the list,  flatten  the list so that all the nodes appear in a single-level, doubly linked list. Let  curr  be a node with a child list. The nodes in the child list should app

This turned out to be a more complicated implementation than I thought, and I think a simple DFS would have been a better choice, but I decided to go with a BFS pushing each node to its own group. Lots of failures and little hacks along the way to make it work, finally it did. Btw, go watch Spider Man No Way Home, top 5 Marvel Movies ever!!! Code is below, cheers, ACC. Is Graph Bipartite? - LeetCode 785. Is Graph Bipartite? Medium 3563 251 Add to List Share There is an  undirected  graph with  n  nodes, where each node is numbered between  0  and  n - 1 . You are given a 2D array  graph , where  graph[u]  is an array of nodes that node  u  is adjacent to. More formally, for each  v  in  graph[u] , there is an undirected edge between node  u  and node  v . The graph has the following properties: There are no self-edges ( graph[u]  does not contain  u ). There are no parallel edges ( graph[u]  does not contain duplicate values). If  v  is in  graph[u] , then  u  is in  graph[v]  (the gra

Shamelessly looked at the hints for this LC hard problem. The hints here actually describe the algorithm step-by-step; it describes the three functions you need to implement (I implemented a fourth one to handle short products). Learned few interesting math concepts by solving this problem, such as how to calculate trailing zeroes quickly and the first five digits of a number using logarithms. Code is down below, cheers, ACC Abbreviating the Product of a Range - LeetCode 2117. Abbreviating the Product of a Range Hard 25 27 Add to List Share You are given two positive integers  left  and  right  with  left <= right . Calculate the  product  of all integers in the  inclusive  range  [left, right] . Since the product may be very large, you will  abbreviate  it following these steps: Count all  trailing  zeros in the product and  remove  them. Let us denote this count as  C . For example, there are  3  trailing zeros in  1000 , and there are  0  trailing zeros in  546 . Denote the remai

Problem involves searching for a min spanning tree in a graph. Basically the algorithm to find the min spanning tree can start from any node in the tree, and it runs in O(n) nodes using BFS. We then try it out by removing each edge at a time, from the back to the front. At the end it should take O(number of nodes * number of edges). Since both are ~10^3, we're talking about 1M interactions, which is relatively fast. Code is down below, cheers, ACC. Redundant Connection - LeetCode 684. Redundant Connection Medium 3161 276 Add to List Share In this problem, a tree is an  undirected graph  that is connected and has no cycles. You are given a graph that started as a tree with  n  nodes labeled from  1  to  n , with one additional edge added. The added edge has two  different  vertices chosen from  1  to  n , and was not an edge that already existed. The graph is represented as an array  edges  of length  n  where  edges[i] = [a i , b i ]  indicates that there is an edge between nodes