Lädt...


🔧 LeetCode Meditations: Number of 1 Bits


Nachrichtenbereich: 🔧 Programmierung
🔗 Quelle: dev.to

Let's start with the description for this one:

Given a positive integer n, write a function that returns the number of set bits in its binary representation (also known as the Hamming weight).

For example:

Input: n = 11
Output: 3

Explanation: The input binary string 1011 has a total of three set bits.

Or:

Input: n = 128
Output: 1

Explanation: The input binary string 10000000 has a total of one set bit.

Or:

Input: n = 2147483645
Output: 30

Explanation: The input binary string 1111111111111111111111111111101 has a total of thirty set bits.

As we mentioned in the chapter introduction in the previous post, a set bit refers to a bit with the value of 1.

So, what we have to do is to count 1 bits.

One way to do it is to convert the number to a string, and just count the 1s. Or, we can convert that to an array and filter out the 0s, and get its length. But, there is another approach where we can use bit manipulation.

We can remove the set bits (bits that have the value 1) until the number becomes 0.

A good thing to know is that n - 1 is the rightmost set removed version of n.

For example, if n is 0010, n - 1 is 0001.

Or, if n is 0110, n - 1 is 0101.

Note
It does not matter whether n - 1 introduces other 1s because we are doing the AND operation to count the set bits.
For example, if n is 0000, then n - 1 is 0111. Their AND will be 0000.
Or, if n is 0010, then n - 1 is 0001. The rightmost set bit of n is 0 in n - 1, and that's all that matters.

We can create a loop that runs as long as there are 1 bits in n, counting each one as we go.
Also each time, we can do an AND operation with n and 1 less of it (n & (n - 1)).

A simple TypeScript solution looks like this:

function hammingWeight(n: number): number {
  let result = 0;
  while (n > 0) {
    n &= (n - 1);
    result++;
  }

  return result;
}
Note
We are using the bitwise AND assignment operator to assign the value to n.

Time and space complexity

The time complexity is, I think, O(log n)O(log \ n) O(log n) — In the worst case when all bits are set, we'll run through the loop log nlog \ n log n times (the number of bits in the binary representation of a number nn n will be log nlog \ n log n ).

The space complexity will be constant ( O(1)O(1) O(1) ) as there is no additional memory usage that will increase as the input increases.

The next problem we'll take a look at is Counting Bits. Until then, happy coding.

...

🔧 LeetCode Meditations: Number of 1 Bits


📈 53 Punkte
🔧 Programmierung

🔧 LeetCode Meditations: Reverse Bits


📈 44.09 Punkte
🔧 Programmierung

🔧 LeetCode Meditations: Reverse Bits


📈 44.09 Punkte
🔧 Programmierung

🔧 LeetCode Meditations: Counting Bits


📈 44.09 Punkte
🔧 Programmierung

🔧 LeetCode Meditations: Counting Bits


📈 44.09 Punkte
🔧 Programmierung

🔧 LeetCode Meditations: Missing Number


📈 40.68 Punkte
🔧 Programmierung

🔧 LeetCode Meditations: Number of Islands


📈 40.68 Punkte
🔧 Programmierung

🔧 LeetCode Meditations: Word Search II


📈 31.77 Punkte
🔧 Programmierung

🔧 LeetCode Meditations: Insert Interval


📈 31.77 Punkte
🔧 Programmierung

🔧 LeetCode Meditations: Subtree of Another Tree


📈 31.77 Punkte
🔧 Programmierung

🔧 LeetCode Meditations: Design Add and Search Words Data Structure


📈 31.77 Punkte
🔧 Programmierung

🔧 LeetCode Meditations: Longest Increasing Subsequence


📈 31.77 Punkte
🔧 Programmierung

🔧 LeetCode Meditations: Same Tree


📈 31.77 Punkte
🔧 Programmierung

🔧 LeetCode Meditations: Implement Trie (Prefix Tree)


📈 31.77 Punkte
🔧 Programmierung

🔧 LeetCode Meditations: Word Break


📈 31.77 Punkte
🔧 Programmierung

🔧 LeetCode Meditations: Maximum Depth of Binary Tree


📈 31.77 Punkte
🔧 Programmierung

🔧 LeetCode Meditations — Chapter 10: Tries


📈 31.77 Punkte
🔧 Programmierung

🔧 LeetCode Meditations: Maximum Product Subarray


📈 31.77 Punkte
🔧 Programmierung

🔧 LeetCode Meditations: Invert Binary Tree


📈 31.77 Punkte
🔧 Programmierung

🔧 LeetCode Meditations: Word Search


📈 31.77 Punkte
🔧 Programmierung

🔧 LeetCode Meditations: Coin Change


📈 31.77 Punkte
🔧 Programmierung

🔧 LeetCode Meditations — Chapter 7: Trees


📈 31.77 Punkte
🔧 Programmierung

🔧 LeetCode Meditations: Combination Sum


📈 31.77 Punkte
🔧 Programmierung

🔧 LeetCode Meditations: Decode Ways


📈 31.77 Punkte
🔧 Programmierung

🔧 LeetCode Meditations: Merge K Sorted Lists


📈 31.77 Punkte
🔧 Programmierung

🔧 LeetCode Meditations — Chapter 9: Backtracking


📈 31.77 Punkte
🔧 Programmierung

🔧 LeetCode Meditations: Palindromic Substrings


📈 31.77 Punkte
🔧 Programmierung

🔧 LeetCode Meditations: Reorder List


📈 31.77 Punkte
🔧 Programmierung

🔧 LeetCode Meditations: Longest Palindromic Substring


📈 31.77 Punkte
🔧 Programmierung

🔧 LeetCode Meditations: Reverse Linked List


📈 31.77 Punkte
🔧 Programmierung

🔧 LeetCode Meditations: Find Median from Data Stream


📈 31.77 Punkte
🔧 Programmierung

🔧 LeetCode Meditations: House Robber II


📈 31.77 Punkte
🔧 Programmierung

🔧 LeetCode Meditations: Two Sum


📈 31.77 Punkte
🔧 Programmierung

🔧 LeetCode Meditations — Chapter 8: Heap/Priority Queue


📈 31.77 Punkte
🔧 Programmierung

matomo