DEV Community

Md. Mohiuddin
Md. Mohiuddin

Posted on

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;
}
Enter fullscreen mode Exit fullscreen mode

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

জোড় সংখ্যা মানে হচ্ছে তার শেষে বাইনারিতে 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];
}
Enter fullscreen mode Exit fullscreen mode

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

LeetCode Problem Link

Image of Wix Studio

2025: Your year to build apps that sell

Dive into hands-on resources and actionable strategies designed to help you build and sell apps on the Wix App Market.

Get started

Top comments (0)

Billboard image

Create up to 10 Postgres Databases on Neon's free plan.

If you're starting a new project, Neon has got your databases covered. No credit cards. No trials. No getting in your way.

Try Neon for Free →

👋 Kindness is contagious

Dive into an ocean of knowledge with this thought-provoking post, revered deeply within the supportive DEV Community. Developers of all levels are welcome to join and enhance our collective intelligence.

Saying a simple "thank you" can brighten someone's day. Share your gratitude in the comments below!

On DEV, sharing ideas eases our path and fortifies our community connections. Found this helpful? Sending a quick thanks to the author can be profoundly valued.

Okay