Another Casual Coder

Another example that requires a quick GCD implementation, back from Euclidian days. Despite the nested loops yielding an N^2 complexity, in addition to the LogN GCD (hence a time complexity of N^2 * LogN), N is relatively small (10^3) leading to a reasonable execution time. Code is below, cheers, ACC. Number of Subarrays With GCD Equal to K - LeetCode 2447. Number of Subarrays With GCD Equal to K Medium 97 31 Add to List Share Given an integer array  nums  and an integer  k , return  the number of  subarrays  of  nums  where the greatest common divisor of the subarray's elements is  k . A  subarray  is a contiguous non-empty sequence of elements within an array. The  greatest common divisor of an array  is the largest integer that evenly divides all the array elements.   Example 1: Input: nums = [9,3,1,2,6,3], k = 3 Output: 4 Explanation: The subarrays of nums where 3 is the greatest common divisor of all the ...

Many times in computer science we're taught to avoid permutations at all costs. This is actually a myth. Permutation is a powerful tool which can be safely applied when the conditions are right. For example, the following problem asks for the total number of valid permutations for a given string to become a valid time. Analyzing the string, you can see that the total possibilities are four question marks which would then entail 10^4, which is 10,000. You can safely try them all using a simple backtracking algorithm, together with StringBuilder for easy manipulation of the string. Code is below, cheers, ACC. Number of Valid Clock Times - LeetCode 2437. Number of Valid Clock Times Easy 109 125 Add to List Share You are given a string of length  5  called  time , representing the current time on a digital clock in the format  "hh:mm" . The  earliest  possible time is  "00:00"  and the  latest  possible time is  "23:59" . In the st...

Simple problem that requires breaking down a number into powers of two. There is a simple algorithm for that, running in LogN. Overall complexity for this problem then becomes NLogN. Code is down below, cheers, ACC. Range Product Queries of Powers - LeetCode 2438. Range Product Queries of Powers Medium 63 8 Add to List Share Given a positive integer  n , there exists a  0-indexed  array called  powers , composed of the  minimum  number of powers of  2  that sum to  n . The array is sorted in  non-decreasing  order, and there is  only one  way to form the array. You are also given a  0-indexed  2D integer array  queries , where  queries[i] = [left i , right i ] . Each  queries[i]  represents a query where you have to find the product of all  powers[j]  with  left i  <= j <= right i . Return  an array  answers , equal in length to  queries , where...

Has been a while (over one year ago) since I've tackled a   Project Euler  (PE) problem. This is my 206th Euler problem solved (after problem 100th, it gets really intense). This one, problem 808, is surprisingly simple. Basically a brute-force solution should do it. I used a combination of MillerRabin Primality Test (LogN) + BigInteger + simple string manipulation functions (palindrome, reverse). Runs in less than one minute. One note thou: I can't post neither the solution (which is a number) nor the code to produce the solution since the PE gods will track you down and suspend your account, so I'll just screenshot the code with some key aspects blurred out. Cheers, ACC. #808 Reversible prime squares - Project Euler

If you follow the hints on the problem, it really becomes super straightforward. Calculate the max chain of good indices towards the left and towards the right in two different O(N)-time loops. Iterate a third time to create the return list. Rest is history. Code is down below, cheers, ACC. Find All Good Indices - LeetCode 2420. Find All Good Indices Medium 251 19 Add to List Share You are given a  0-indexed  integer array  nums  of size  n  and a positive integer  k . We call an index  i  in the range  k <= i < n - k   good  if the following conditions are satisfied: The  k  elements that are just  before  the index  i  are in  non-increasing  order. The  k  elements that are just  after  the index  i  are in  non-decreasing  order. Return  an array of all good indices sorted in  increasing  order .   Example 1: Input...

A so-called hard problem but in reality a straightforward Trie implementation. Typical Trie where the very first element (root) is ignored and you use a hashtable for the children. In this case here keep track of the score as you add all the words. Works super fast in execution time O(sizeWord * numberWords) or 1M (max) steps. Code is down below, cheers, ACC. Sum of Prefix Scores of Strings - LeetCode 2416. Sum of Prefix Scores of Strings Hard 226 20 Add to List Share You are given an array  words  of size  n  consisting of  non-empty  strings. We define the  score  of a string  word  as the  number  of strings  words[i]  such that  word  is a  prefix  of  words[i] . For example, if  words = ["a", "ab", "abc", "cab"] , then the score of  "ab"  is  2 , since  "ab"  is a prefix of both  "ab"  and  "abc" . Return  an array  answer  ...

Standard BFS for this problem: keep a list of all the odd elements and whenever you switch state (meaning moving to an even level - reminds me of a little bit of FSM), then you can "reverse the list". Make sure to do one more time outside of the main queue loop for the case where the last level is an odd one. Code is down below, cheers, ACC. Reverse Odd Levels of Binary Tree - LeetCode 2415. Reverse Odd Levels of Binary Tree Medium 150 3 Add to List Share Given the  root  of a  perfect  binary tree, reverse the node values at each  odd  level of the tree. For example, suppose the node values at level 3 are  [2,1,3,4,7,11,29,18] , then it should become  [18,29,11,7,4,3,1,2] . Return  the root of the reversed tree . A binary tree is  perfect  if all parent nodes have two children and all leaves are on the same level. The  level  of a node is the number of edges along the path between it and the root node.   Example...