Numbers With Repeated Digits - Digit DP [JS]

By on

Description 

Solution: Digit DP

Memoize each dp(i, mask, state, hasRepeat), where

  • i = the ith digit

  • mask = bitmask which indicates which digit we have already used

  • state = indicates whether the current number is tracking smaller, equal, or greater than n

    • 0 = smaller
    • 1 = equal
    • 2 = greater

  • hasRepeat = whether we have a repeated digit

If hasRepeat is true (1), count it as 1 way.
For each state, count the total number of ways after appending each digit (0 - 9).

state:

  • If digit < n[index], update state to 0 (smaller) if state is currently 1 (equal).
  • If digit === n[index], keep state the same.
  • If digit > n[index], update state to 2 (greater) if state is currently 1 (equal).

d = number of digits in n
Time Complexity: O(d * 2^10 * 3 * 2 * 10) 488ms
d * 2^10 * 3 * 2 = the number of different states we can have
10 = at each state we have 10 options for digits 0-9
Space Complexity: O(d * 2^10 * 3 * 2) 62MB

var numDupDigitsAtMostN = function(n) {
  let str = n.toString(), size = str.length, memo = new Map();
  return dp(0, 0, 1, 0);
  
  function dp(i, mask, state, hasRepeat) {
    if (i === size) return state < 2 && hasRepeat ? 1 : 0;
    let key = `${i},${mask},${state},${hasRepeat}`;
    if (memo.has(key)) return memo.get(key);
    
    let ans = hasRepeat;
    for (let digit = 0; digit <= 9; digit++) {
      if (i === 0 && digit === 0) continue;
      let newMask = mask | (1 << digit), repeat = hasRepeat || (mask === newMask ? 1 : 0);
      if (digit < Number(str[i])) {
        ans += dp(i + 1, newMask, state === 1 ? 0 : state, repeat);
      } else if (digit === Number(str[i])) {
        ans += dp(i + 1, newMask, state, repeat);
      } else {
        ans += dp(i + 1, newMask, state === 1 ? 2 : state, repeat);
      }
    }
    memo.set(key, ans);
    return ans;
  }  
};

javascript
Location: Auckland, New Zealand

Comments

Post a Comment

Popular posts from this blog

Minimum Number of Operations to Sort a Binary Tree by Level - BFS & Cycle Counting Explained [JS]

By on
Description   Solution: BFS & Cycle Counting BFS level-by-level and get minimum swaps for the node values at each level. How to calculate the minimum swaps to sort an array: Get the index of each number in its sorted position (store in a hashmap  indexes ) For each  nums[i] , store the number we need to swap with to place  nums[i]  in its sorted position (store in a hashmap  next ) Find the size of each cycle. Get the total sum of each ( cycle size - 1 ). Why sum of ( cycle size - 1 ) is correct: If cycle size =  1 , we don't need any swaps. If cycle size =  2 , we only need 1 swap. If cycle size =  3 , we need 2 swaps. ---  Main Proof  --- Starting from the smallest number in the cycle, swap each  nums[i]  (where  nums[i]  is in the cycle) into its sorted position. Since the number is now in the correct position, it is no longer in the cycle and this leaves us with a cycle of size ( n - 1 ), where  n = ...
Read more

Beautiful Towers II - Monotonic Increasing Stack [JS]

By on
Description   Solution: Monotonic Increasing Stack Find the maximum possible sum of heights ending and starting at each index  i . left :  left[i]  = sum of heights from ( 0, ..., i ) such that they are descending from index  i  to  0 . right :  right[i]  = sum of heights from ( i, ..., n - 1 ) such that they are descending from index  i  to  n - 1 . Use a monotonic increasing stack to store indices of  maxHeights  such that they are smaller than  maxHeights[i] . left to right: We know that from index  i  to  stack[stack.length - 1] , all heights are smaller than  maxHeights[i] . Take the existing sum up to  stack[stack.length - 1]  ( left[stack[stack.length - 1]] ) and add the sum for the current range ( maxHeights[i] * (i - stack[stack.length - 1]) ) Then, do the same from right to left. Take each  maxHeights[i]  as the peak of the mountain and use the results from  ...
Read more

Reschedule Meetings for Maximum Free Time I - Sliding Window - Constant Space [JS]

By on
Description   Solution: Sliding Window Maintain a sliding window of size  k + 2  and store the running sum of meetings within the window. Within each window, move all meetings as left as possible or right as possible such that there is no space in between the meetings. This maximizes the longest continuous gap. This can be calculated by: last meeting start time - first meeting end time - sum of meeting durations in between first and last meetings. Time Complexity:  O(n) Space Complexity:  O(1) JavaScript function maxFreeTime ( eventTime , k , startTime , endTime ) { const n = startTime . length ; let durationSum = 0 , maxGap = 0 ; for ( let i = 0 ; i < n ; i ++ ) { durationSum += endTime [ i ] - startTime [ i ] ; if ( i >= k ) { durationSum -= endTime [ i - k ] - startTime [ i - k ] ; } if ( i >= k - 1 ) { const lastMeetingStart = i === n - 1 ? eventTime : startTime [ i +...
Read more

Maximum Sum of Distinct Subarrays With Length K - Sliding Window w/ Two Pointers & Set [JS]

By on
Description  Solution: Sliding Window w/ Two Pointers & Set Maintain a sliding window of unique numbers with maximum size of  k . We can store the numbers in the window in a hashset. When we move the right pointer up, move the left pointer up until: all numbers in the window are unique the window size  <= k Time Complexity:  O(n)  246ms Space Complexity:  O(k)  71.5MB var maximumSubarraySum = function ( nums, k ) { let set = new Set (), sum = 0 ; let ans = 0 , n = nums.length; for ( let j = 0 , i = 0 ; j < n; j++) { sum += nums[j]; while (set.has(nums[j]) || j - i >= k) { sum -= nums[i]; set.delete(nums[i]); i++; } set.add(nums[j]); if (j - i + 1 === k) ans = Math .max(ans, sum); } return ans; };
Read more

Sum of Prefix Scores of Strings - Trie [JS]

By on
Description   Solution: Trie Store each word in a trie. For every node in the trie, keep track of the number of words it is part of. Since we stored the count of words on every node, we can calculate the count of every prefix for every word on the fly. n = number of words ,  m = max(words[i].length) Time Complexity:  O(nm) Space Complexity:  O(26^m)  at worst var sumPrefixScores = function ( words ) { let trie = new Trie(); for ( let word of words) { trie.add(word); } let n = words.length, res = Array (n); for ( let i = 0 ; i < words.length; i++) { res[i] = trie.getScore(words[i]); } return res; }; class TrieNode { constructor ( ) { this .children = {}; this .count = 0 ; } } class Trie { constructor ( ) { this .root = new TrieNode(); } add ( word ) { let node = this .root; for ( let i = 0 ; i < word.length; i++) { node = node.children; let char = word[i]; if (...
Read more