Count the Digits That Divide a Number - Modulo 10 [JS]

By on

Description 

Solution: Modulo 10

Find the last digit of the number: n % 10.
Use Math.floor(n / 10) to remove the last digit.
Repeat this until n becomes 0.

Time Complexity: O(log(n)) 58ms
Space Complexity: O(1) 41.7MB

var countDigits = function(num) {
  let n = num, ans = 0;
  while (n > 0) {
    let digit = n % 10;
    if (num % digit === 0) ans++;
    n = Math.floor(n / 10);
  }
  return ans;
};
Location: Auckland, New Zealand

Comments

Post a Comment

Popular posts from this blog

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

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

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

Maximum Score After Applying Operations on a Tree - DFS [JS]

By on
Description   Solution: Post-order DFS Choose one node value to keep per leaf node path. Use post-order DFS to find the minimum sum of node values taking one node per path (at the end, the result is  total sum - dfs(0, -1) ) For each  dfs(node) , we have two choices: Take the node: We get to keep all the subtree values except the current node. Skip the node: Each child subtree needs to choose one value to keep. n = number of nodes ,  m = number of edges Time Complexity:  O(n + m) Space Complexity:  O(n + m) var maximumScoreAfterOperations = function ( edges, values ) { let n = values.length, graph = Array (n).fill( 0 ).map( () => []); for ( let [a, b] of edges) { graph[a].push(b); graph[b].push(a); } let totalSum = values.reduce( ( sum, value ) => sum + value); return totalSum - dfs( 0 , - 1 ); function dfs ( node, parent ) { if (graph[node].length === 1 && graph[node][ 0 ] === parent) { return va...
Read more

Divide Nodes Into the Maximum Number of Groups - Union Find & BFS [JS]

By on
Description   Solution: Union Find & BFS Build the graph and connect nodes using union find. Find the groups of connected nodes. Find the maximum groups to divide for each connected group. Use level-by-level BFS to find the maximum depth of the group. How to detect an odd-lengthed cycle: Cycles are bound to meet in the middle since we are traversing level-by-level, so if the level of a neighbor node is equal to the current level, the cycle is odd-lengthed. n = number of nodes ,  m = number of edges Time Complexity:  O(n * (n + m))  639ms Space Complexity:  O(n + m)  64.6MB var magnificentSets = function ( n, edges ) { let uf = new UnionFind(n + 1 ); let graph = Array (n + 1 ).fill( 0 ).map( () => []); for ( let [a, b] of edges) { // 1. Build graph, connect nodes graph[a].push(b); graph[b].push(a); uf.union(a, b); } let groups = {}; for ( let i = 1 ; i <= n; i++) { // 2. Find groups of connected nodes let...
Read more