Part 15 · Lesson 58 · read
Tries and Bit Manipulation
Prefix trees, and the bit tricks that interviews ask about.
On this page
Why a trie?
Imagine a dictionary of 100,000 words. You ask: "does any word start with pre?" (A prefix is the beginning of a word.) Checking every word takes O(number of words) time. A trie (say "try"; it is also called a prefix tree) is a better way: a tree where each node stands for one more character of a word. It stores words as paths through a tree (a structure of nodes, where each node links down to its child nodes), and each step is one character. Words that start the same way share the same path. Think of a phone book where all the names starting with “Sm” sit together. Now the question costs only O(length of the prefix), however many words are stored. Autocomplete, spell checkers and word-game solvers use this idea.
Building a trie
Each node holds its children. This is a Map (a built-in JavaScript object that stores key-value pairs, and looks up a value by its key) that links a character to the next node. Each node also has a flag called isEnd. It says if a stored word finishes at that node. The flag is needed. After you insert "apple", the nodes for "a", "ap", "app" and "appl" all exist. But only "apple" is a word.
All three operations (insert, search and startsWith) walk down from the root, one character at a time. So each takes O(L) time for a word with L letters. Memory is O(total characters stored) in the worst case. It is less when words share the same start.
// A trie (prefix tree): every node is one character; a path from the root spells a prefix.class TrieNode { constructor() { this.children = new Map(); // character -> TrieNode this.isEnd = false; // true if a stored word ends exactly here }}class Trie { constructor() { this.root = new TrieNode(); } insert(word) { let node = this.root; for (const ch of word) { if (!node.children.has(ch)) node.children.set(ch, new TrieNode()); node = node.children.get(ch); } node.isEnd = true; } // Follow the characters of s from the root; return the last node, or null if the path breaks. #walk(s) { let node = this.root; for (const ch of s) { node = node.children.get(ch); if (node === undefined) return null; } return node; } search(word) { // is this exact word stored? const node = this.#walk(word); return node !== null && node.isEnd; } startsWith(prefix) { // does any stored word begin with prefix? return this.#walk(prefix) !== null; }}const trie = new Trie();trie.insert("apple");console.log(trie.search("apple")); // trueconsole.log(trie.search("app")); // false ("app" is only a prefix so far)console.log(trie.startsWith("app")); // truetrie.insert("app");console.log(trie.search("app")); // trueMap works for any alphabet and stores only the letters that appear. If the input is only lowercase English letters, you can use an array with 26 slots instead (children[ch.charCodeAt(0) - 97]). This is common and a little faster. The logic is the same.Traced: insert and search
Only the root exists. It stands for the empty prefix (nothing typed yet). In the variable panel, a * at the end marks a node where a word ends.
▶for (const word of ["cat", "car"]) {2 let node = root;3 for (const ch of word) {4 if (!node.children.has(ch)) node.children.set(ch, new TrieNode());5 node = node.children.get(ch);6 }7 node.isEnd = true;8}9// now search("ca"):10node = root;11for (const ch of "ca") node = node.children.get(ch);12console.log(node.isEnd);| trie | "(empty)" |
Wildcard search with DFS
Now let the search pattern contain ., which means "any one letter". A normal letter has exactly one way to go. A dot could be any child, so we must try all of them. This is a depth-first search (DFS). You follow one branch as deep as it goes. If it fails, you go back up and try the next branch. It is like exploring a maze: walk down one corridor until it ends, then return and try another. The recursion (a function that calls itself) keeps track of the node and the position in the pattern.
// Words can be added normally; searches may contain "." which matches any single letter.class WordDictionary { constructor() { this.root = { children: new Map(), isEnd: false }; } addWord(word) { let node = this.root; for (const ch of word) { if (!node.children.has(ch)) node.children.set(ch, { children: new Map(), isEnd: false }); node = node.children.get(ch); } node.isEnd = true; } search(pattern) { const dfs = (node, i) => { if (i === pattern.length) return node.isEnd; // consumed the whole pattern: it must end a word const ch = pattern[i]; if (ch === ".") { for (const child of node.children.values()) { // wildcard: try every branch if (dfs(child, i + 1)) return true; } return false; } const child = node.children.get(ch); return child !== undefined && dfs(child, i + 1); // normal letter: follow the one matching branch }; return dfs(this.root, 0); }}const dict = new WordDictionary();dict.addWord("bad"); dict.addWord("dad"); dict.addWord("mad");console.log(dict.search("pad")); // falseconsole.log(dict.search("bad")); // trueconsole.log(dict.search(".ad")); // trueconsole.log(dict.search("b..")); // trueconsole.log(dict.search("b.")); // false (too short)Without dots, a search takes O(L). With dots it can visit many branches. In the worst case, a pattern of only dots explores every node down to depth L (the pattern length). That is at most O(total characters stored).
Bits and operators in JavaScript
Computers store whole numbers as bits (binary digits, each one a 0 or a 1). Think of a row of light switches that are either off (0) or on (1). The number 5 is 101: one 4, no 2, and one 1. We count bit positions from the right, starting at 0. So in 101, bits 0 and 2 are set (on). JavaScript has these bitwise operators(operators that work on each bit):
| Operator | Name | Result bit is... | Typical use |
|---|---|---|---|
| & | AND | 1 if both bits are 1 | check bits or keep only some bits (masking) |
| | | OR | 1 if either bit is 1 | set bits |
| ^ | XOR | 1 if the bits differ | flip bits; cancel pairs |
| ~ | NOT | flip all 32 bits (~n = -n - 1) | make masks such as ~(1 << i) |
| << | shift left | move bits up, fill with 0 | 1 << i makes a mask with one bit on |
| >> | signed shift right | move bits down, copy the sign bit into the gap | halve a number, rounding down |
| >>> | unsigned shift right | move bits down, fill with 0 | read 32 bits as a positive number (n >>> 0) |
console.log(5 & 3); // 1 AND: 1 only where both bits are 1 101 & 011 = 001console.log(5 | 3); // 7 OR: 1 where either bit is 1 101 | 011 = 111console.log(5 ^ 3); // 6 XOR: 1 where the bits differ 101 ^ 011 = 110console.log(~5); // -6 NOT: flips every one of the 32 bits (this equals -n - 1)console.log(5 << 1); // 10 shift left: multiplies by 2 (while it still fits in 32 bits)console.log(5 >> 1); // 2 shift right: divides by 2 and rounds downconsole.log(7 .toString(2)); // 111 a number as a binary stringconsole.log(parseInt("1011", 2)); // 11 a binary string as a numberconsole.log(0b1010, 0xff); // 10 255 binary and hexadecimal literalsThe 32-bit rule
This detail surprises many people. A JavaScript number is normally a 64-bit decimal-style value (floating point). But every bitwise operator first turns its inputs into 32-bit signed integers. “Signed” means the number can be negative. The form used is called two's complement, which is the usual way computers store negative numbers. In it, the top bit (bit 31) is the sign. If that bit is on, the number is negative. The result is also a 32-bit signed integer, from -2147483648 to 2147483647. This has three effects:
- Too-big numbers turn negative:
1 << 31is-2147483648, not 2147483648. - Big values are cut off: only the lowest 32 bits are kept, so
2 ** 32 + 5 | 0is5. Numbers beyond 232 lose their high bits, and there is no warning. Whole numbers above 253 - 1 are not even exact as a normal number. - Shift counts wrap around: the count is taken modulo 32 (the remainder after dividing by 32). So
1 << 32equals1 << 0, which is 1.
>> (signed shift) copies the sign bit into the empty places, so negative numbers stay negative. >>> (unsigned shift) fills the empty places with zeros and gives a result from 0 to 4294967295. The common trick n >>> 0 turns a 32-bit pattern into a positive number.
// JavaScript numbers are 64-bit floating point, but every bitwise operator first converts its// operands to a 32-bit SIGNED integer (two's complement), works on those 32 bits, and gives back// a 32-bit signed result: a number from -2147483648 to 2147483647.console.log(1 << 30); // 1073741824console.log(1 << 31); // -2147483648 bit 31 is the sign bit, so the result turns negativeconsole.log(1 << 32); // 1 the shift count is taken modulo 32, so this is 1 << 0// >> keeps the sign (copies the top bit in); >>> fills with zeros, treating the 32 bits as UNSIGNEDconsole.log(-8 >> 1); // -4console.log(-8 >>> 1); // 2147483644console.log(-1 >>> 0); // 4294967295 "n >>> 0" reinterprets a 32-bit pattern as an unsigned numberconsole.log((-5 >>> 0).toString(2)); // 11111111111111111111111111111011 the 32 bits of -5// Anything outside 32 bits is silently truncated to its low 32 bits (a number is also cut to an integer first)console.log(2 ** 32 + 5 | 0); // 5 2^32 is a bit 33 positions up; it vanishesconsole.log(2 ** 31 | 0); // -2147483648 2^31 does not fit in a signed 32-bit integerconsole.log(2 ** 53 | 0); // 0 the low 32 bits of 2^53 are all zeroconsole.log(3.7 | 0, -3.7 | 0); // 3 -3 the fraction is dropped (this truncates towards zero)// Precedence trap: comparison binds tighter than &, so always bracket the bit operation.console.log(4 & 1 === 0); // 0 parsed as 4 & (1 === 0), i.e. 4 & falseconsole.log((4 & 1) === 0); // trueIf you really need more than 32 bits, use BigInt (a number type for very big whole numbers). Its operators have no 32-bit limit:
// For true 64-bit work, use BigInt: add n to a number literal and use the same operators.console.log(1n << 40n); // 1099511627776nconsole.log((2n ** 64n) - 1n); // 18446744073709551615nCheck, set, clear, toggle
Four operations cover most needs: check a bit, set it (turn it on), clear it (turn it off), and toggle it (flip it). The key tool is a mask. A mask is a number made to touch only some bits, like a stencil that lets paint through only in some places. 1 << i is the mask with only bit i switched on.
const n = 0b1010; // 10, bits (from the right, position 0) are: 0 1 0 1// check bit i: shift it to position 0, then keep only that bitconsole.log((n >> 1) & 1); // 1 bit 1 is setconsole.log((n >> 2) & 1); // 0 bit 2 is clear// set bit i: OR with a mask that has only bit i switched onconsole.log(n | (1 << 2)); // 14 0b1110// clear bit i: AND with a mask that has every bit EXCEPT i switched onconsole.log(n & ~(1 << 1)); // 8 0b1000// toggle bit i: XOR with the single-bit maskconsole.log(n ^ (1 << 3)); // 2 0b0010console.log(n ^ (1 << 0)); // 11 0b1011// lowest set bit: n & -n keeps only the rightmost 1console.log(12 & -12); // 4 12 is 0b1100Counting set bits
A bit that equals 1 is called a set bit. The expression n & (n - 1) removes the lowest set bit. Here is why. Subtracting 1 turns that bit into 0, and turns every zero below it into 1. Then the AND wipes out exactly that part. So if you loop until n is 0, the loop runs once for each set bit.
// Brian Kernighan's trick: n & (n - 1) clears the lowest set bit.// Why: subtracting 1 turns the lowest 1 into 0 and every 0 below it into 1; AND removes the whole stretch.function countBits(n) { let count = 0; while (n !== 0) { n = n & (n - 1); // one set bit removed per loop count++; } return count; // runs once per SET bit, not once per bit position}console.log(countBits(44)); // 3 44 is 0b101100console.log(countBits(0)); // 0console.log(countBits(4294967293)); // 31 0xFFFFFFFD: the whole 32 bits except one| Step | n & (n - 1) | count | Meaning |
|---|---|---|---|
| start | 101100 (44) | 0 | three 1-bits to remove |
| n & (n - 1) | 101100 & 101011 = 101000 (40) | 1 | the lowest 1 (value 4) is removed |
| n & (n - 1) | 101000 & 100111 = 100000 (32) | 2 | the next lowest 1 (value 8) is removed |
| n & (n - 1) | 100000 & 011111 = 000000 (0) | 3 | n is 0, so stop. The answer is 3 |
Each loop removes the lowest 1 and nothing else. 44 has three 1-bits, so there are exactly three loops.
The simple way checks every bit position. Notice the unsigned shift. It makes sure the loop still ends for a negative input:
// The straightforward way: look at the last bit, then shift it away.function countBitsShift(n) { let count = 0; while (n !== 0) { count += n & 1; n >>>= 1; // UNSIGNED shift: with >> a negative number would never reach 0 } return count;}console.log(countBitsShift(44)); // 3console.log(countBitsShift(4294967293)); // 31Power of two, XOR and the single number
A power of two (1, 2, 4, 8, 16 and so on) has exactly one set bit, like 1000. So n & (n - 1) clears it and leaves 0. Add n > 0 to rule out zero and negative numbers.
// A power of two has exactly one set bit, so removing it leaves 0.function isPowerOfTwo(n) { return n > 0 && (n & (n - 1)) === 0;}console.log(isPowerOfTwo(16)); // true 0b10000 & 0b01111 = 0console.log(isPowerOfTwo(18)); // false 0b10010 & 0b10001 = 0b10000console.log(isPowerOfTwo(1)); // true 2^0console.log(isPowerOfTwo(0)); // falseconsole.log(isPowerOfTwo(-8)); // false n > 0 rejects negatives (and keeps 0, where 0 & -1 is 0, from counting)& sees only the lowest 32 bits. So this trick is safe for inputs up to 231 - 1, which is what interview problems promise. Take a value like 2 ** 32 + 1. Here n - 1 = 2 ** 32. Both numbers are cut to 32 bits before the AND, so the test would wrongly return true. For more than 32 bits, use BigInt or a different method.XOR (^) has three properties worth remembering: a ^ a = 0, a ^ 0 = a, and the order does not matter. Now take an array where every value appears twice, except one. XOR all the values together. The pairs cancel each other, and only the odd one out is left. This takes O(n) time and O(1) memory:
// Every number appears twice except one. XOR has three useful properties:// a ^ a = 0 a ^ 0 = a and the order does not matter.// So the pairs cancel and the loner is left.function singleNumber(nums) { let result = 0; for (const x of nums) result ^= x; return result;}console.log(singleNumber([4, 1, 2, 1, 2])); // 4console.log(singleNumber([2, 2, 1])); // 1console.log(singleNumber([7])); // 7Subsets with bitmasks
You met subsets in lesson 33, where we used backtracking. Bits give another way that needs only a loop. With n items there are 2n subsets. Each number from 0 to 2n - 1, written in binary, tells you which items to take. If bit i is set, item i is in the subset. This works only for small n. There are 2n subsets, so about 20 is the practical limit. Also, 1 << n must fit in 32 bits, so n can be at most 30.
// n items => 2^n subsets. Read the binary digits of a mask from 0 to 2^n - 1:// bit i set means "item i is in the subset".function subsets(items) { const n = items.length; const result = []; for (let mask = 0; mask < (1 << n); mask++) { const subset = []; for (let i = 0; i < n; i++) { if ((mask >> i) & 1) subset.push(items[i]); } result.push(subset); } return result;}console.log(subsets(["a", "b", "c"]));// [ [], [ 'a' ], [ 'b' ], [ 'a', 'b' ], [ 'c' ], [ 'a', 'c' ], [ 'b', 'c' ], [ 'a', 'b', 'c' ] ]Practice questions
For the trie questions, first draw the tree for two or three words. For the bit questions, first write the numbers in binary on paper. Then write the code.
Design a Trie class with insert(word), search(word) (true only if exactly that word was inserted) and startsWith(prefix) (true if any inserted word begins with the prefix, which is the start of a word).
Hint 1
Hint 2
Hint 3
Show all 3 solutions with explanations
Store every word in a Set (a built-in collection that keeps each value once and checks whether a value is in it in about O(1) time). search is a quick lookup. startsWith checks the beginning of every word, one by one.
class Trie { constructor() { this.words = new Set(); } insert(word) { this.words.add(word); } search(word) { return this.words.has(word); } startsWith(prefix) { for (const w of this.words) if (w.startsWith(prefix)) return true; return false; }}const t = new Trie();t.insert("apple");console.log(t.search("apple")); // trueconsole.log(t.search("app")); // falseconsole.log(t.startsWith("app")); // truet.insert("app");console.log(t.search("app")); // trueThis is correct. But each startsWith call takes O(total characters stored). A trie exists to avoid exactly this.
A node holds a Map of children and an isEnd flag. One shared helper walks along a string. It returns the node where the walk ends, or null if the path breaks.
class TrieNode { constructor() { this.children = new Map(); this.isEnd = false; }}class Trie { constructor() { this.root = new TrieNode(); } insert(word) { let node = this.root; for (const ch of word) { if (!node.children.has(ch)) node.children.set(ch, new TrieNode()); node = node.children.get(ch); } node.isEnd = true; } walk(s) { let node = this.root; for (const ch of s) { node = node.children.get(ch); if (node === undefined) return null; } return node; } search(word) { const node = this.walk(word); return node !== null && node.isEnd; } startsWith(prefix) { return this.walk(prefix) !== null; }}const t = new Trie();t.insert("apple");console.log(t.search("apple")); // trueconsole.log(t.search("app")); // falseconsole.log(t.startsWith("app")); // truet.insert("app");console.log(t.search("app")); // trueEach operation takes O(L) for a word with L letters, however many words are stored. Memory is O(total characters inserted) in the worst case.
If the input is only lowercase English letters, use a fixed array of 26 slots instead of a Map. The index of a letter is its character code minus the code of "a".
class Trie { constructor() { this.children = new Array(26).fill(null); this.isEnd = false; } // each Trie object is also a node insert(word) { let node = this; for (const ch of word) { const i = ch.charCodeAt(0) - 97; if (node.children[i] === null) node.children[i] = new Trie(); node = node.children[i]; } node.isEnd = true; } walk(s) { let node = this; for (const ch of s) { node = node.children[ch.charCodeAt(0) - 97]; if (node === null) return null; } return node; } search(word) { const node = this.walk(word); return node !== null && node.isEnd; } startsWith(prefix) { return this.walk(prefix) !== null; }}const t = new Trie();t.insert("apple");console.log(t.search("apple")); // trueconsole.log(t.search("app")); // falseconsole.log(t.startsWith("app")); // truet.insert("app");console.log(t.search("app")); // trueThe time is the same O(L), and finding a child is faster. But every node reserves 26 slots even if it has only one child. So it uses more memory when the trie is thin. It also works only for lowercase letters.
Use the Map trie. It works for any characters and is easy to read. Mention the 26-slot array version as the usual choice for lowercase input. (LeetCode 208.)
Design a structure with addWord(word) and search(pattern). A pattern may contain the character ., which matches any one letter. search returns true if some stored word matches the whole pattern.
Hint 1
Hint 2
Hint 3
Show all 2 solutions with explanations
Keep the words in an array. For each word with the same length, compare it with the pattern letter by letter. Treat . as a match for any letter.
class WordDictionary { constructor() { this.words = []; } addWord(word) { this.words.push(word); } search(pattern) { for (const w of this.words) { if (w.length !== pattern.length) continue; let ok = true; for (let i = 0; i < w.length; i++) { if (pattern[i] !== "." && pattern[i] !== w[i]) { ok = false; break; } } if (ok) return true; } return false; }}const d = new WordDictionary();d.addWord("bad"); d.addWord("dad"); d.addWord("mad");console.log(d.search("pad")); // falseconsole.log(d.search("bad")); // trueconsole.log(d.search(".ad")); // trueconsole.log(d.search("b..")); // trueEach search takes O(N × L) for N stored words of length L. It is simple and fine for small inputs. But a trie avoids looking at words that cannot match.
Build a trie. To search, use recursion (a function that calls itself) with (node, position). A normal letter follows its one child. A dot tries every child and succeeds if any child succeeds. At the end of the pattern, succeed only if the node marks the end of a word.
class WordDictionary { constructor() { this.root = { children: new Map(), isEnd: false }; } addWord(word) { let node = this.root; for (const ch of word) { if (!node.children.has(ch)) node.children.set(ch, { children: new Map(), isEnd: false }); node = node.children.get(ch); } node.isEnd = true; } search(pattern) { const dfs = (node, i) => { if (i === pattern.length) return node.isEnd; if (pattern[i] === ".") { for (const child of node.children.values()) if (dfs(child, i + 1)) return true; return false; } const child = node.children.get(pattern[i]); return child !== undefined && dfs(child, i + 1); }; return dfs(this.root, 0); }}const d = new WordDictionary();d.addWord("bad"); d.addWord("dad"); d.addWord("mad");console.log(d.search("pad")); // falseconsole.log(d.search("bad")); // trueconsole.log(d.search(".ad")); // trueconsole.log(d.search("b..")); // trueconsole.log(d.search("b.")); // falseA pattern without dots costs O(L). With dots the search can spread out and, in the worst case, visit every node of the trie. But it skips (prunes) any branch where the letter does not match. The recursion goes at most L calls deep (the pattern length), which is small.
The trie with depth-first search is the answer interviewers expect. Skipping bad branches is what makes it better than scanning the whole list. Be ready to say what the worst case is for a pattern of only dots. (LeetCode 211.)
Every element of nums appears exactly twice, except one element that appears once. Return that element. If you can, use linear time (one pass) and constant extra memory.
Hint 1
Hint 2
x ^ x? What is x ^ 0?Hint 3
Show all 3 solutions with explanations
Count how many times each value appears. Then return the value that appears once.
function singleNumber(nums) { const counts = new Map(); for (const x of nums) counts.set(x, (counts.get(x) ?? 0) + 1); for (const [value, count] of counts) if (count === 1) return value;}console.log(singleNumber([2, 2, 1])); // 1console.log(singleNumber([4, 1, 2, 1, 2])); // 4console.log(singleNumber([7])); // 7O(n) time, but O(n) extra memory for the Map.
Add up the different values and double the result. Subtract the real sum. What is left is exactly the single number: 2 × sum(set) - sum(nums).
function singleNumber(nums) { const distinct = new Set(nums); let twice = 0, total = 0; for (const x of distinct) twice += 2 * x; for (const x of nums) total += x; return twice - total;}console.log(singleNumber([2, 2, 1])); // 1console.log(singleNumber([4, 1, 2, 1, 2])); // 4console.log(singleNumber([7])); // 7O(n) time, O(n) memory. This is a nice trick, but it still uses a Set.
With XOR, equal values cancel each other (x ^ x = 0). Zero changes nothing, and the order does not matter. So if you XOR the whole array, only the single value is left.
function singleNumber(nums) { let result = 0; for (const x of nums) result ^= x; return result;}console.log(singleNumber([2, 2, 1])); // 1console.log(singleNumber([4, 1, 2, 1, 2])); // 4console.log(singleNumber([7])); // 7O(n) time and O(1) memory. It works for values inside the 32-bit signed range, which the problem promises. Beyond that range, JavaScript's bitwise operators cut the number to 32 bits and the result would be wrong.
XOR is the answer the question is looking for (linear time, constant memory). If you want a safe start, begin with the Map and then improve it. (LeetCode 136.)
Given a whole number n that is zero or more (treat it as an unsigned 32-bit value, which means it cannot be negative), return the number of 1 bits in its binary form.
Hint 1
n & 1, then shift. Which shift operator is safe for big inputs?Hint 2
n & (n - 1) do to the lowest set bit?Show all 3 solutions with explanations
Add n & 1 to the count. Shift right with the unsigned operator. Repeat until n is 0.
function hammingWeight(n) { let count = 0; while (n !== 0) { count += n & 1; n >>>= 1; // unsigned: the sign bit does not stick } return count;}console.log(hammingWeight(11)); // 3console.log(hammingWeight(128)); // 1console.log(hammingWeight(4294967293)); // 31At most 32 loops, so O(1) for a fixed bit size. The >>> matters. With >>, a value like 4294967293 (which the operators see as the negative number -3) would keep copying the sign bit and never reach 0.
n & (n - 1) removes the lowest 1. Count how many times you can do this before n becomes 0.
function hammingWeight(n) { let count = 0; while (n !== 0) { n &= n - 1; count++; } return count;}console.log(hammingWeight(11)); // 3console.log(hammingWeight(128)); // 1console.log(hammingWeight(4294967293)); // 31One loop for each set bit, so there are fewer loops for numbers with few 1s. It also works for values that look negative. The operators work on the 32-bit pattern, which is why 4294967293 still gives 31.
Turn the number into binary text and count the "1" characters.
function hammingWeight(n) { return n.toString(2).split("").filter((ch) => ch === "1").length;}console.log(hammingWeight(11)); // 3console.log(hammingWeight(128)); // 1console.log(hammingWeight(4294967293)); // 31This is correct for inputs that are zero or more, and quick to write. But it makes a string and an array. It is not the answer an interviewer wants, though it is fine for checking your work.
Use n &= n - 1 and explain why it clears one bit in each loop. That is the idea this question tests. Remember the shift version as the simple alternative. (LeetCode 191.)
Given a whole number n, return an array ans of length n + 1, where ans[i] is the number of 1 bits in the binary form of i.
Hint 1
Hint 2
i >> 1 filled in before i in the answer array?Hint 3
bits[i] equals bits[i >> 1] plus the dropped bit, which is i & 1.Show all 3 solutions with explanations
For each i from 0 to n, count its set bits with the n & (n - 1) loop.
function countBits(n) { const result = []; for (let i = 0; i <= n; i++) { let x = i, count = 0; while (x !== 0) { x &= x - 1; count++; } result.push(count); } return result;}console.log(countBits(2)); // [ 0, 1, 1 ]console.log(countBits(5)); // [ 0, 1, 1, 2, 1, 2 ]O(n × k), where k is the number of bits (at most about 17 for typical limits). That is about O(n log n). It is correct, but it wastes work that neighbouring numbers could share.
i >> 1 is i without its last bit. It is smaller than i, so its count is already known. Add 1 if the last bit (i & 1) was set.
function countBits(n) { const bits = new Array(n + 1).fill(0); for (let i = 1; i <= n; i++) bits[i] = bits[i >> 1] + (i & 1); return bits;}console.log(countBits(2)); // [ 0, 1, 1 ]console.log(countBits(5)); // [ 0, 1, 1, 2, 1, 2 ]O(n) time, and the output array is the only memory used. Example: bits[5] = bits[2] + 1 = 1 + 1 = 2.
i & (i - 1) is i with its lowest set bit removed, and it is smaller than i. So bits[i] = bits[i & (i - 1)] + 1.
function countBits(n) { const bits = new Array(n + 1).fill(0); for (let i = 1; i <= n; i++) bits[i] = bits[i & (i - 1)] + 1; return bits;}console.log(countBits(2)); // [ 0, 1, 1 ]console.log(countBits(5)); // [ 0, 1, 1, 2, 1, 2 ]This is also O(n). Example: bits[6] = bits[4] + 1 = 2, because 6 is 110 and clearing its lowest 1 gives 100.
Either DP version is the expected answer (O(n), with no separate loop for each number). Pick the one you can explain more clearly. (LeetCode 338.)
Given a whole number n, return true if it is a power of two (that is, n = 2^k for some whole number k >= 0). Otherwise return false.
Hint 1
Hint 2
Hint 3
Show all 3 solutions with explanations
A power of two becomes 1 if you halve it again and again. If a number becomes odd before it reaches 1, it is not a power of two.
function isPowerOfTwo(n) { if (n <= 0) return false; while (n % 2 === 0) n /= 2; return n === 1;}console.log(isPowerOfTwo(1)); // trueconsole.log(isPowerOfTwo(16)); // trueconsole.log(isPowerOfTwo(3)); // falseconsole.log(isPowerOfTwo(0)); // falseconsole.log(isPowerOfTwo(-8)); // falseO(log n) time and O(1) memory. It uses no bit tricks, so the 32-bit cut-off of bitwise operators cannot hurt it.
A positive power of two has a single set bit. n & (n - 1) clears it and leaves 0. Any other positive number still has a bit left.
function isPowerOfTwo(n) { return n > 0 && (n & (n - 1)) === 0;}console.log(isPowerOfTwo(1)); // trueconsole.log(isPowerOfTwo(16)); // trueconsole.log(isPowerOfTwo(3)); // falseconsole.log(isPowerOfTwo(0)); // falseconsole.log(isPowerOfTwo(-8)); // falseO(1) time and memory. You need the n > 0 check. Without it, 0 would pass, because 0 & -1 is 0. The trick is safe for inputs inside the 32-bit signed range, which the problem promises. Outside that range (for example 2^32 + 1), the numbers are cut to 32 bits and the answer can be wrong.
Count the 1 bits with the clear-lowest-bit loop from question 4. A positive power of two has exactly one.
function isPowerOfTwo(n) { if (n <= 0) return false; let ones = 0; while (n !== 0) { n &= n - 1; ones++; } return ones === 1;}console.log(isPowerOfTwo(1)); // trueconsole.log(isPowerOfTwo(16)); // trueconsole.log(isPowerOfTwo(3)); // falseconsole.log(isPowerOfTwo(0)); // falseconsole.log(isPowerOfTwo(-8)); // falseThis is also correct and shows the idea. But it is just a longer way to do the same one test.
Give the one-line bit trick and explain it. It is the expected answer. The dividing loop is the safe back-up. (LeetCode 231.)
Given an array nums with n different numbers from the range [0, n], return the one number in the range that is missing from the array.
Hint 1
Hint 2
Hint 3
Show all 3 solutions with explanations
Put the numbers in a Set. Then check each value from 0 to n.
function missingNumber(nums) { const seen = new Set(nums); for (let v = 0; v <= nums.length; v++) if (!seen.has(v)) return v;}console.log(missingNumber([3, 0, 1])); // 2console.log(missingNumber([0, 1])); // 2console.log(missingNumber([9, 6, 4, 2, 3, 5, 7, 0, 1])); // 8O(n) time and O(n) memory.
0 + 1 + ... + n equals n(n + 1) / 2. Subtract the real sum of the array. What is left is the missing number.
function missingNumber(nums) { const n = nums.length; let sum = 0; for (const x of nums) sum += x; return (n * (n + 1)) / 2 - sum;}console.log(missingNumber([3, 0, 1])); // 2console.log(missingNumber([0, 1])); // 2console.log(missingNumber([9, 6, 4, 2, 3, 5, 7, 0, 1])); // 8O(n) time and O(1) memory. The totals stay far below 2^53, which is the limit for exact whole numbers in JavaScript, for any realistic n.
Start with n. XOR in every index i and every value nums[i]. Every number from 0 to n appears twice (once as an index or as the start value, and once as a value). The missing number appears only once, so it is what is left.
function missingNumber(nums) { let result = nums.length; for (let i = 0; i < nums.length; i++) result ^= i ^ nums[i]; return result;}console.log(missingNumber([3, 0, 1])); // 2console.log(missingNumber([0, 1])); // 2console.log(missingNumber([9, 6, 4, 2, 3, 5, 7, 0, 1])); // 8O(n) time, O(1) memory, and there is no risk of a huge sum. For [3,0,1]: 3 ^ (0^3) ^ (1^0) ^ (2^1) = 2.
The sum formula is the shortest. XOR uses the same idea as Single Number, where pairs cancel. Naming it shows that you see the link. (LeetCode 268.)
Make it stick
- Write a Trie class with insert, search and startsWith from memory. Say what
isEndis for. - Explain how a
.in a pattern turns the search into a depth-first search over the children. - State the 32-bit rule. Say what happens to
1 << 31and to2 ** 32 + 5 | 0, and whatn >>> 0does. - Write the four mask operations: check, set, clear and toggle (flip) bit i.
- Explain why
n & (n - 1)clears the lowest set bit. Use it to count bits and to test for powers of two. - Explain why XOR finds the number that appears only once.
Revisit schedule: solve two of the questions again tomorrow, again in 3 days, and once more in a week — without looking at the answers. Each time it will feel easier. That is the memory forming.
What's next
You now have every technique in this series. Lesson 59, The Interview Playbook, is about using them when you feel pressure. It covers what to ask, how to explain a brute-force (try everything) answer, how to write clean code and test it with a dry run, and how to use hints.
Practise on LeetCode
Real interview problems that use exactly what this lesson teaches. Solve them in JavaScript after the practice questions above.
Published by Jainik · Last updated · How these lessons are made
Keep learning
Part of the study guide
Related series