Posts

Showing posts from May, 2019

Largest Prime Removing Digits From Left-Hand End

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);

Remove All Adjacent Duplicates In String

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

Last Stone Weight, an easy LeetCode problem

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 get 1 so the array converts to [1,1,1] then, we combine 1 and 1 to get 0 so the array converts

From N! to N^2 (Dynamic Programming)

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 previous solu

Best way to deal with floating numbers: don't

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