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