Another Casual Coder

Not super fast solution here, pretty much O(nlogn) for an N=10^4, using pQueue. Here is the gist of it: 1/ It is a graph problem where you need to assign the largest number to the node with the most number of connections 2/ Use a hash table to implement the graph (hash of hash) 3/ Build the graph using #2 4/ Using a pQueue (descended order), add the cities based on the number of connections (as the weight) 5/ Dequeue and assign the different values for the cities ([n..1]) 6/ Traverse the graph again adding up the importance. Need to ensure that the same road isn't counted twice (another hash table of "visited") Code is down below, cheers, ACC. Maximum Total Importance of Roads - LeetCode 2285. Maximum Total Importance of Roads Medium 173 6 Add to List Share You are given an integer  n  denoting the number of cities in a country. The cities are numbered from  0  to  n - 1 . You are also given a 2D integer array  roads  where  roads[i] = [a i , b i ]  denotes that there exi

Riemann's Zeta Function is at the center of the Riemann's Hypothesis which says that all the zeroes for the Zeta Function are of the form ki + 1/2 (in other words, the real part of all zeroes for the Zeta Function is 1/2). The importance of this hypothesis is that, if confirmed to be true (which most mathematicians believe it to be true), it can provide a very well-defined structure for the constructions of Prime Numbers. For example, one of the corollaries of proving the Riemann hypothesis is that we'll have a precise way to determine the number of primes less than a given M. Hence one can then use this formula to calculate any number of primes between two given numbers N and M. The mathematical importance of finding a well-structured behavior for prime numbers is monumental: prime numbers are the basis of number theory, and despite them being infinite (proved first by Euclid in 300 BCE) and seeming random, it is believed that they follow a somewhat (yet to be understood)

This problem interestingly enough requires a quick implementation of the millennium-old GCD - Greatest Common Divisor. It is a geometric problem where what you need to do is check whether point V2 belongs to the same line as points V1 and V0. In order to do so, and to avoid floating-point arithmetic, keep track of the slope of V1 and V0 using the num/den fraction, but reduce it to its irreducible form. In order to do so, you'll need to calculate the GCD between num and den. That can be done using Euclid's algorithm which runs in LogN. Since there is a sorting pre-step involved, the total execution time would be NLogN. Code is down below, cheers, ACC. Minimum Lines to Represent a Line Chart - LeetCode 2280. Minimum Lines to Represent a Line Chart Medium 152 326 Add to List Share You are given a 2D integer array  stockPrices  where  stockPrices[i] = [day i , price i ]  indicates the price of the stock on day  day i  is  price i . A  line chart  is created from the array by plotti

Given a number N, create a random binary tree with the numbers [1..N]. It can actually be done in NLogN time. 1/ Have an index at 2 (assuming root = 1. This can be modified if needed by shuffling the numbers 1..N at a pre-step) 2/ The outer loop will continue until index reaches N, hence O(N) 3/ The inner loop is the most interesting one. It will traverse down the tree randomly trying to go either left or right, placing the current (ref-based) index there 4/ Notice that in #3, the max distance that the inner loop will travel is the height of the tree, which will be on average O(Log(N)) 5/ Putting that altogether, you have an NLogN algorithm 6/ Once can also force a "lean left" or "lean right" during the randomness. This will force the tree to be larger towards the left or right. Using a value in the middle (50) ensures uniform distribution Code is down below.  I miss my father. He passed away on 5/18/2022 after a long battle in the ICU. Eternally loved. ACC. public

Another typical prefix sum problem (O(n)-time, O(n)-space). Code is down below, cheers, ACC. Number of Ways to Split Array - LeetCode 2270. Number of Ways to Split Array Medium 34 3 Add to List Share You are given a  0-indexed  integer array  nums  of length  n . nums  contains a  valid split  at index  i  if the following are true: The sum of the first  i + 1  elements is  greater than or equal to  the sum of the last  n - i - 1  elements. There is  at least one  element to the right of  i . That is,  0 <= i < n - 1 . Return  the number of  valid splits  in   nums .   Example 1: Input: nums = [10,4,-8,7] Output: 2 Explanation: There are three ways of splitting nums into two non-empty parts: - Split nums at index 0. Then, the first part is [10], and its sum is 10. The second part is [4,-8,7], and its sum is 3. Since 10 >= 3, i = 0 is a valid split. - Split nums at index 1. Then, the first part is [10,4], and its sum is 14. The second part is [-8,7], and its sum is -1. Sinc

It is the digit 1 (one) Code below calculates the probability, and of course this isn't any random generator, but rather Random.Next() in C#. Number #1 wins by far (close to 80%) leaving the second place (#2, no pun intended) way behind with 64% probability. I'm sure that the mathematical explanation is trivial... Cheers, ACC foreach (char digit in "0123456789") { Random rd = new Random(); int count = 0; int M = 10000000; for (int i = 0; i < M; i++) { int n = rd.Next(); string temp = n.ToString(); if (temp.Contains(digit)) { count++; } } Console.WriteLine("Probability to contain {0}: {1}%", digit, count * 100.0 / M); }