0 থেকে n পর্যন্ত সংখ্যার প্রতিটিতে 1 bit কতবার আছে বের করা

আমরা recursion and dynamic programming ব্যবহার করে সহজেই এটার সমাধান O(nlogn) complexity তে বের করতে পারি। এক্ষেত্রে আমরা যেভাবে স্বাভাবিকভাবে bit সংখ্যা বের করি সেভাবেই চিন্তা করতে পারি। অর্থাৎ প্রতিবার ভাগ করতে থাকব এবং ভাগশেষ টাকে count করব। যেমনঃ

25 % 2 = 1 25 / 2 = 12
12 % 2 = 0 12/ 2 = 6
6 % 2 = 0 3/2 = 1
1 % 2 = 1 1/2 = 0

এখানে আমরা যদি আমরা set bit পাই তাহলে বিট সংখ্যা 1 বৃদ্ধি পাবে। অন্যথায় তার সেট বিট সংখ্যা তার অর্ধেক সংখ্যার সমান।

char bit[(int)1e5 + 1];

int getBit(int n) {
    if (n == 0)
        return 0;

    if (bit[n] == 0) {
        return bit[n] = (n & 1) + getBit(n / 2);
    }

    return bit[n];
}

vector<int> countBits(int n) {
    vector<int> x;
    for (int i = 0; i <= n; i++) {
        x.push_back(getBit(i));
    }
    return x;
}

কিন্তু আমরা আরেকটু চিন্তা করতে চাই।

জোড় সংখ্যা মানে হচ্ছে তার শেষে বাইনারিতে 0 থাকবে। যেমন,

0 : 0000
2 : 0010
4 : 0100
6 : 0110
8 : 1000

আবার কোন সংখ্যাকে আমরা দ্বিগুণ করতে চাই তখন আমরা কী করি? তার শেষে একটা 0 লাগিয়ে দেই। যেমন,


1: 0
2: 10
5: 101
10: 1010

তার মানে কোন সংখ্যাকে ২ দিয়ে ভাগ করার অর্থ হল তার থেকে একটা 0 কমিয়ে দেওয়া। যেমন,

12: 1100
6: 110

আসলে এক্ষেত্রে 1 এর সংখ্যা কিন্তু কমছেও না বাড়ছেও না।

কিন্তু আমরা যদি জোড় সংখ্যার সাথে একটা 1 যুক্ত করি তার মানে নতুন সংখ্যায় আগেরটার চেয়ে একটা 1 বেড়ে গেল। এটাই হচ্ছে এই প্রবলেমের সবচেয়ে মজার দিক। যেমন,

10: 1010 (2 set bit)
11: 1011 (3 set bit)
12: 1100 (2 set bit)
13: 1101 (1 set bit)


তাহলে আমাদের এবার আর logn extra complexity লাগছে না। আমাদের প্রবলেমটা এখন O(n) (প্রতিটি element আমরা একবার access করব) complexity তেই সমাধান করা যাচ্ছে। Function টা এখন আমরা এভাবে লিখতে পারি-

int getBit(int n) {
    if (n == 0)
        return bit[0] = 0;

    if (n & 1) { // ood number
        return bit[n] = bit[n - 1] + 1;
    }
    return bit[n] = bit[n / 2];
}

অর্থাৎ জোড় হলে সে যার দ্বিগুণ তার bit সংখ্যার সমান। আর যদি বেজোড় সংখ্যা হয় তাহলে আগের জোড় সংখ্যার সাথে শুধু ১ যোগ হবে শেষে। তার মানে একটা 1 বিট বেড়ে গেল।

LeetCode Problem Link