3
\$\begingroup\$

I solve this problem in Swift. I am looking for a code review, thanks!

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.

class Solution {
    func countBits(num: Int) -> [Int] {
        var nums = [Int](count: num+1, repeatedValue: 0)
        if num == 0 { // if num is 0
            return nums
        }
        for i in 1...num {
            nums[i] = binaryOnes(i)
        }
        return nums
    }
    func binaryOnes(num: Int) -> Int {
        var num = num
        var count = 0
        repeat  {
            if num % 2 == 0 { // even numbers
                num /= 2
            } else { // all odd numbers
                num = (num-1)/2
                count += 1
            }
        } while num > 1
        if num == 1 { // when num is 1 at the end
            count += 1
        }
        return count
    }
}
\$\endgroup\$
4
\$\begingroup\$

Both methods don't use any state of the Solution class, so they should be static methods of that type, or global functions.

binaryOnes() can be simplified. If you replace

repeat { ... } while num > 1

by

while num > 0 { ... }

then the additional check for num == 1 becomes obsolete:

func binaryOnes(num: Int) -> Int {
    var num = num
    var count = 0
    while num > 0 {
        if num % 2 == 0 { // even numbers
            num /= 2
        } else { // all odd numbers
            num = (num-1)/2
            count += 1
        }
    }
    return count
}

Now observe that num % 2 gives the least significant bit of the number (0 or 1), and num /= 2 is a truncating division. Therefore the function can be simplified to

func binaryOnes(num: Int) -> Int {
    var num = num
    var count = 0
    while num > 0 {
        count += num % 2
        num /= 2
    }
    return count
}

More sophisticated bit counting methods can be found at https://graphics.stanford.edu/~seander/bithacks.html, they can be more effective for large numbers.

In countBits, the check for num == 0 is not necessary, because 1...num is the empty range in that case:

func countBits(num: Int) -> [Int] {
    var nums = [Int](count: num+1, repeatedValue: 0)
    for i in 1...num {
        nums[i] = binaryOnes(i)
    }
    return nums
}

Calling the variables num and nums could be confusing, upTo: might be a better name for the parameter.

But what the function actually does is to map the numbers 0...upTo to their bit count. That can be done directly with a map() method:

func countBits(upTo: Int) -> [Int] {
    return (0...upTo).map(binaryOnes)
}

An alternative approach would be to use the fact that

bitCount(n) = bitCount(n/2) + (n % 2)

for all (positive) integers n. Together with bitCount(0) = 0 this is a recursive computation method. But since you store the bit counts in an array anyway, this can be implemented as a simple iteration:

func countBits1(upTo: Int) -> [Int] {
    var result = [ 0 ]
    for i in 1...upTo {
        result.append(result[i/2] + (i % 2))
    }
    return result
}

Now the binaryOnes() function is not needed anymore.

\$\endgroup\$
0
\$\begingroup\$

// ********* 338. Counting Bits *********

The previous solution will fail for the input [0].

func countBits(_ num: Int) -> [Int] {
    var result = [0]
    guard num != 0 else {
        return result
    }
    for i in 1...num {
        result.append(result[i/2] + (i % 2))
    }
    return result
}
\$\endgroup\$
  • \$\begingroup\$ You have presented an alternative solution, but haven't reviewed the code. Please edit to show what aspects of the question code prompted you to write this version, and in what ways it's an improvement over the original. It may be worth (re-)reading How to Answer. \$\endgroup\$ – Toby Speight Jul 22 '19 at 16:05
  • 1
    \$\begingroup\$ @TobySpeight Thanks for the constructive criticism. Yup I wrote it like stack-overflow and not like code-review. Will take your suggestion for my future responses. \$\endgroup\$ – user550088 Jul 22 '19 at 18:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.