CountingBits338.kt

package easy

/**
 * Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.



Example 1:

Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10
Example 2:

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101


Constraints:

0 <= n <= 105


Follow up:

It is very easy to come up with a solution with a runtime of O(n log n). Can you do it in linear time O(n) and possibly in a single pass?
Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?
 */
fun countBits(n: Int): IntArray {
    val result = mutableListOf<Int>()
    for( i in 0..n)
    {
        result.add(i.countOneBits())
    }
    return result.toIntArray()
}

fun Int.countOneBits():Int
{
    var count=0
    var  num=this
    while (num!=0)
    {
        if(num%2==1)
            count++
        num/=2
    }
    return count
}

// Solution with T = O(N)
fun countBitsSol2(n: Int): IntArray {
    val result = IntArray(n+1)
    for( i in 1..n)
    {
        result[i]=i.countBits()
    }
    return result
}
// using And Algorithm
fun Int.countBits():Int
{
    var count=0
    var  num=this
    while (num!=0)
    {
        num=num.and(num-1)
        count++
    }
    return count
}