Posts

A non-recursive trick for subsets generation IV

-
Another problem that requires subset generation, and the same non-recursive technique is applied: go from 0 to 2^N-1, creating the subsets. N=12 so very small. I could have used StringBuilder to reduce the mem and processing pressure, but string worked fine too. Code is down below, cheers, ACC. Valid Binary Strings With Cost Limit - LeetCode You are given two integers n and k . The cost of a binary string s is defined as the sum of all indices i (0-based) such that s[i] == '1' . A binary string is considered valid if: It does not contain two consecutive '1' characters. Its cost is less than or equal to k . Return a list of all valid binary strings of length n in any order.   Example 1: Input: n = 3, k = 1 Output: ["000","010","100"] Explanation: The binary strings of length 3 without consecutive '1' characters are: "000" : cost = 0 " 100" : cost = 0 "010" : cost = 1 "001" : cost...
Post a Comment
Read more

The Sieve (but not Eratosthenes')

-
Sieves are a technique in algorithms that lets you build a certain pattern from the ground up in NLogN. The most famous one is the Sieve of Eratosthenes, which lets you compute the prime (or actually the !primes) in NLogN. But you can use Sieves for other problems unrelated to primes. The one below is a good example. The NLogN comes simply from the inner loop condition which goes only to maxVal but it grows very fast, hence this condition here is the key to achieving the LogN (the N comes from the outer loop). Code is down below, cheers, ACC. Minimize Array Sum Using Divisible Replacements - LeetCode You are given an integer array nums . You can perform the following operation any number of times: Choose two indices a and b such that nums[a] % nums[b] == 0 . Replace nums[a] with nums[b] . Return the minimum possible sum of the array after performing any number of operations.   Example 1: Input: nums = [3,6,2] Output: 7 Explanation: Choose a = 1 , b = 2 , where nums[a] = 6 an...
Post a Comment
Read more