CODEWITHSUNDEEP
javaalgorithm
Prathamesh N
Prathamesh N

Reputation: 1

Reducing time complexity of the code (max execution time is 16000 ms)

Can someone help me out how to reduce time complexity of this code. Max execution time is 16000 ms.

public class count {

    public static void main(String[] args) {
        long c = 0;
        
        for(long i=1L;i<=200000000000000L;i++) {
            c+=Long.bitCount((i));
        }
        
        System.out.println(c);
    }
}

Upvotes: 0

Views: 86

Answers (1)

dan1st
dan1st

Reputation: 16373

There is 1 number with just one bit (number 1, excluding 0). Then, there are 2 numbers with exactly two bits (2 and 3) After that, 4 numbers with exactly three bits exist (4, 5, 6 and 7) and it continues this way.

In general, there are 2 to the power of n-1 numbers with n bits. Knowing this, you can calculate the number of bits by getting the number of bits of the last number and adding the bit counts of all previous numbers afterwards:

public class count {

    public static void main(String[] args) {
        long lastNum=200000000000000L;
        long bc=Long.bitCount(lastNum);
        long c=bc;
        //1<<n means 2 to the power of n
        c*=1L<<(c-1);//2 to the power of c-1 is the first number with c bits
        for(long l=1;l<bc;l++){//all numbers of bits until the 
            c+=l*(1L<<(l-1));
        }
        System.out.println(c);
    }
}

The time complexity of this code is O(log(n)) as bc is the binary logarithm of n and it loops from 1 to bc and all other operations in the loop are constant.

Upvotes: 1

Related Questions