আমাদের একটি জাভাস্ক্রিপ্ট ফাংশন লিখতে হবে যা একটি সংখ্যা গ্রহণ করবে। ফাংশনটি নিচের নিয়মাবলী অনুযায়ী সংখ্যাটি চাঙ্কে ভাগ করবে -
- চাঙ্কের সংখ্যা পাওয়ার-অফ-টু হবে,
- প্রতিটি চাঙ্কের আইটেম সংখ্যাও পাওয়ার-অফ-টু হবে (সাইজ मैक्स পাওয়ার অফ টু পর্যন্ত, ১, ২, ৪, ৮, ১৬, ৩২, ৩২ হলো ম্যাক্স)
অতএব, উদাহরণস্বরূপ, ৮ হলে ১ চাঙ্কে -
[8]
৯ হলে -
[8, 1]
এটি কাজ করে কারণ দুটি সংখ্যাও পাওয়ার অফ টু, এবং অ্যারে সাইজ ২ (পাওয়ার অফ টু)।
১১ ট্রাই করি -
[8, 2, 1]
এটি কাজ করে না। কারণ অ্যারে সাইজ ৩ যা পাওয়ার অফ টু নয়, যদিও যোগফল ১১।
[4, 4, 2, 1]
এটি কাজ করে! এতে ৪টি এলিমেন্ট আছে যা পাওয়ার অফ টু।
উদাহরণ
function permuteCombinations(n, maximum){
const maxPowerOf2 = 1 << maximum;
const m = ~~(n / maxPowerOf2);
const A = new Array(maximum + 1).fill(0);
A[maximum] = m;
let num = n - m * maxPowerOf2;
let p = 0;
let bitCount = 0;
while (num){
if (num & 1){
bitCount += 1;
A[p] = 1;
}
num >>= 1;
p += 1;
}
const min = m + bitCount;
let target = 1;
while (target < min) target *= 2;
if (target > n) return -1;
if (target == min) return A.map((c, p) => [1 << Number(p), c]);
if (target == n) return [n];
target = target - min;
let i = m ? maximum : p;
while (target && i > 0){
if (!A[i]){
i -= 1;
continue;
}
const max = Math.min(target, A[i]);
A[i] -= max;
A[i-1] += 2*max;
target -= max;
i -= 1;
}
return target ? -1 : A.map((c, p) => [1 << Number(p), c]);
};
console.log(permuteCombinations(11, 5));
আউটপুট
কনসোলে আউটপুট হবে -
[ [1, 1], [2, 1], [4, 2], [8, 0], [16, 0], [32, 0] ]
