Another Casual Coder

Recently on Fermat's Library in Twitter , the following curiosity was posted: What if we tried the same but from the left-hand end? For example, "113" would be a candidate because: 113 is prime   13 is prime     3 is prime What's the largest of such a value? Is the a max one? Well let's leave the digit "zero" aside for now since we're looking to have unique numbers at each step of the sequence. There is actually a Max value for that! Here it is: 357686312646216567629137 Code to find it is down below - it uses BigInteger and Miller-Rabin for quick primality test. Also, DFS with pruning. Equally interesting as the twitter post. Cheers, ACC. using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Numerics; namespace FermatLibraryProblem { class Program { static void Main(string[] args) { BigInteger max = 0; Process(0, 1, ref max); ...

Here is the problem:  https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string/ Given a string  S  of lowercase letters, a  duplicate removal  consists of choosing two adjacent and equal letters, and removing them. We repeatedly make duplicate removals on S until we no longer can. Return the final string after all such duplicate removals have been made.  It is guaranteed the answer is unique. Example 1: Input: "abbaca" Output: "ca" Explanation: For example, in "abbaca" we could remove "bb" since the letters are adjacent and equal, and this is the only possible move.  The result of this move is that the string is "aaca", of which only "aa" is possible, so the final string is "ca". Note: 1 <= S.length <= 20000 S  consists only of English lowercase letters. Given the S.length off the order of 20K, an N^2 solution would be intractable. Best is to think about this problem as ...

Happy Sunday, folks! In this problem, there is a very simple data structure that can be used. Here is the problem:  https://leetcode.com/problems/last-stone-weight/ We have a collection of rocks, each rock has a positive integer weight. Each turn, we choose the two  heaviest  rocks and smash them together.  Suppose the stones have weights  x  and  y  with  x <= y .  The result of this smash is: If  x == y , both stones are totally destroyed; If  x != y , the stone of weight  x  is totally destroyed, and the stone of weight  y  has new weight  y-x . At the end, there is at most 1 stone left.  Return the weight of this stone (or 0 if there are no stones left.) Example 1: Input: [2,7,4,1,8,1] Output: 1 Explanation: We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then, we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then, we combine 2 and 1 to ...

Here is the problem:  https://leetcode.com/problems/jump-game/ Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index. Example 1: Input: [2,3,1,1,4] Output: true Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index. Example 2: Input: [3,2,1,0,4] Output: false Explanation: You will always arrive at index 3 no matter what. Its maximum   jump length is 0, which makes it impossible to reach the last index. Normally this would be an N! solution: for each element i you can try i-1 permutations for a total of N*(N-1)*(N-2)*....*1 = N!. Using DP you can optimize this significantly, from exponential to polynomial. Assume that you have the solution for all indexes 0, 1, 2, ...., N-1. Hence the solution for N will follow the following rule:  - Go to all...

Here is the problem:  https://leetcode.com/problems/valid-boomerang/ A  boomerang  is a set of 3 points that are all distinct and  not  in a straight line. Given a list of three points in the plane, return whether these points are a boomerang. Example 1: Input: [[1,1],[2,3],[3,2]] Output: true Example 2: Input: [[1,1],[2,2],[3,3]] Output: false Note: points.length == 3 points[i].length == 2 0 <= points[i][j] <= 100 Although this is a super easy problem, there is one learning here: whenever you think about having float numbers in your code, try to avoid them. You'll get bogged down into rounding problems left and right. Just do your calculations on a paper, remove the divisions, and end up with a simple integer equation. Also, go up a notch in terms of the data type that you're using in order to avoid overflow, hence if the input is "int", work with "long". As simple as that. Code's below, many cheers, ACC. public c...

The problem comes from Daily Coding Problem, here it is: Good morning! Here's your coding interview problem for today. This problem was asked by Google. Implement a  PrefixMapSum  class with the following methods: insert(key: str, value: int) : Set a given key's value in the map. If the key already exists, overwrite the value. sum(prefix: str) : Return the sum of all values of keys that begin with a given prefix. For example, you should be able to run the following code: mapsum.insert("columnar", 3) assert mapsum.sum("col") == 3 mapsum.insert("column", 2) assert mapsum.sum("col") == 5 One way to solve this is to build a prefix trie in the following way: Start with a simple trie implementation: hash table for the children nodes, the cumulative val, whether the node is a word, and the value of the word When adding the word, set the cumulative along the way and check whether the current node is a word If it is, mak...

Solving Collatz Conjecture  could bring instant happiness to your life... Fine, maybe not happiness, but approximately $1,000,000.00 based on my estimates of how famous you'll be. Let's start with the conjecture, then we'll talk more: prove that the code below always ends for any positive integer Professor Collatz came up with this conjecture when he was only 22 years old, in 1932, while working on some graph construction problems. He himself made no progress in solving it. Almost 100 years later, and still very little progress has been made. It is one of the simplest open problems in modern mathematics, and yet one for which mathematicians have little to no clue on how to even begin to tackle it. I wrote the code below to calculate it (also known as "the 3x+1 conjecture"), and using BigIntegers, you can try really big numbers. No matter how large you try, as far as I know, it always stops.... Cheers, ACC. Collatz.exe 12332112332112332112332112332112...