এখানে, আমাদের একটি প্রোগ্রাম লিখতে হবে যা দেওয়া নাম্বারটি ৩-এর গুণফল কিনা তা চেক করবে।
এক জেনারেল সমাধান হল ট্রivial সমাধান, নাম্বারের সব ডিজিট যোগ করা এবং যদি সমটি ৩-এর গুণফল হয় তবে নাম্বারটি ৩ দিয়ে বিভাজ্য অন্যথায় না। কিন্তু এই সমাধানটি সবচেয়ে ইফিশিয়েন্ট নয়।
একটি ইফিশিয়েন্ট সমাধান হবে নাম্বারের বাইনারি রিপ্রেজেন্টেশনে সেট বিটের কাউন্ট ব্যবহার করা। যদি অড পজিশনে সেট বিটের কাউন্ট এবং ইভেন পজিশনে সেট বিটের কাউন্টের পার্থক্য ৩-এর গুণফল হয় তবে নাম্বারটি ৩-এর গুণফল।
আমরা একটি লুপ ব্যবহার করব এবং নাম্বারের বিটগুলো শিফ্ট করব এবং ইভেন এবং অড পজিশনে সেট বিটের সংখ্যা কাউন্ট করব। শেষে, আমরা চেক করব পার্থক্যটি ৩-এর গুণফল কিনা।
একটি উদাহরণ দিয়ে ইমপ্লিমেন্টেশন বুঝতে পারি,
ইনপুট
n = 24
আউটপুট
even
ব্যাখ্যা
binary representation = 11000 Even set bits = 1, odd set bits = 1. Difference = 0, it is divisible.
আমাদের সমাধানের ইমপ্লিমেন্টেশন দেখানোর প্রোগ্রাম,
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int isDivisibleBy3(int n) {
int oddBitCount = 0;
int evenBitCount = 0;
if (n < 0)
n = -n;
if (n == 0)
return 1;
if (n == 1)
return 0;
while (n) {
if (n & 1)
oddBitCount++;
if (n & 2)
evenBitCount++;
n = n >> 2;
}
return isDivisibleBy3(oddBitCount - evenBitCount);
}
int main() {
int n = 1241;
cout << "The number " << n;
if (isDivisibleBy3(n))
cout << " is a multiple of 3";
else
cout << " is not a multiple of 3";
return 0;
}
আউটপুট
The number 1241 is not a multiple of 3
