ভাগফলের চেয়ে বেশি সেট বিট থাকা ভাজকের সংখ্যা গণনা (C++)

একটি পূর্ণসংখ্যা N দেওয়া আছে যা ভাজক হিসেবে বিবেচিত হবে। এটিকে ১ থেকে N পর্যন্ত সংখ্যাগুলো দিয়ে ভাগ করা হবে এবং কাজ হল সেই ভাজকদের সংখ্যা বের করা যাদের সেট বিটের সংখ্যা ভাগফলের সেট বিটের চেয়ে বেশি।

উদাহরণ

ইনপুট - int N = 6

আউটপুট - ভাগফলের চেয়ে বেশি সেট বিট থাকা ভাজকের সংখ্যা: 5

ব্যাখ্যা - N কে ১ থেকে N পর্যন্ত ভাগ করে ভাজক এবং ভাগফলের সেট বিট তুলনা করা হলো:

• ১ → 6/1(1) = 6(2) → 1 < 2 = বিবেচনা নয়
• ২ → 6/2(1) = 3(2) → 2 = 2 = বিবেচনা
• ৩ → 6/3(2) = 2(1) → 2 > 1 = বিবেচনা
• ৪ → 6/4(1) = 1(1) → 1 = 1 = বিবেচনা
• ৫ → 6/5(2) = 1(1) → 2 > 1 = বিবেচনা
• ৬ → 6/6(2) = 1(1) → 2 > 1 = বিবেচনা

বিবেচিত مواردের সংখ্যা ৫।

ইনপুট - int N = 10

আউটপুট - ভাগফলের চেয়ে বেশি সেট বিট থাকা ভাজকের সংখ্যা: 8

ব্যাখ্যা - একইভাবে ১০ কে ১ থেকে ১০ পর্যন্ত ভাগ করে যাচাই করলে ৮টি কেস বিবেচিত হয়।

প্রোগ্রামে ব্যবহৃত পদ্ধতি

• পজিটিভ ইন্টিজার N ইনপুট নিয়ে divisors_quotient() ফাংশনে পাস করুন।
• ফাংশন divisors_quotient() ভিতরে: N - set_quo(N) + 1 রিটার্ন করুন।
• ফাংশন set_quo() ভিতরে:
  • টেম্পোরারি ভেরিয়েবল start=1, end=sqrt(N)।
  • হোয়াইল লুপ: start < end। temp = (start+end)/2।
  • যদি verify(temp, N) সত্য হয় তবে end = temp, অন্যথায় start = temp+1।
  • যদি !verify(start, N) হয় তবে start+1 রিটার্ন করুন, অন্যথায় start।
• ফাংশন verify() ভিতরে: val_bit(temp/val) <= val_bit(val) হলে true রিটার্ন করুন।
• ফাংশন val_bit() ভিতরে:
  • কাউন্ট ভেরিয়েবল ডিক্লেয়ার করুন।
  • হোয়াইল লুপ: val থাকা পর্যন্ত। val = val/2 করুন এবং কাউন্ট বাড়ান।
  • কাউন্ট রিটার্ন করুন।

উদাহরণ কোড

#include <bits/stdc++.h>
using namespace std;

int val_bit(int val) {
    int count = 0;
    while (val) {
        val = val / 2;
        count++;
    }
    return count;
}

bool verify(int val, int temp) {
    if (val_bit(temp / val) <= val_bit(val)) {
        return true;
    }
    return false;
}

int set_quo(int N) {
    int start = 1;
    int end = sqrt(N);
    while (start < end) {
        int temp = (start + end) / 2;
        if (verify(temp, N)) {
            end = temp;
        } else {
            start = temp + 1;
        }
    }
    if (!verify(start, N)) {
        return start + 1;
    } else {
        return start;
    }
}

int divisors_quotient(int N) {
    return N - set_quo(N) + 1;
}

int main() {
    int N = 10;
    cout << "Count of divisors having more set bits than quotient on dividing N are: " << divisors_quotient(N);
    return 0;
}

উপরের কোড রান করলে নিচের আউটপুটটি পাওয়া যাবে:

আউটপুট

Count of divisors having more set bits than quotient on dividing N are: 8