সমস্যা
আমাদের একটি জাভাস্ক্রিপ্ট ফাংশন লিখতে হবে যা একটি স্ট্রিং, অ্যাআর, 0 এবং 1 ব্যবহার করে গঠিত হয় শুধুমাত্র প্রথম আর্গুমেন্ট হিসাবে।
ফাংশনটি দ্বিতীয় এবং তৃতীয় আর্গুমেন্ট হিসাবে যথাক্রমে m এবং দুটি সংখ্যা নেয়। আমাদের ফাংশনের কাজ হল সর্বাধিক m 0s এবং n 1s ব্যবহার করে অ্যারে অ্যারের থেকে কতগুলি স্ট্রিং তৈরি করা যায় তা খুঁজে বের করা৷
উদাহরণস্বরূপ, যদি ফাংশনে ইনপুট হয় −
const arr = ["10", "0001", "111001", "1", "0"]; const m = 5, n = 3;
তারপর আউটপুট −
হওয়া উচিতconst output = 4;
আউটপুট ব্যাখ্যা:
মোট 4টি স্ট্রিং আছে যা 5 0s এবং 3 1s ব্যবহার করে গঠিত হতে পারে, যা হল −
“10,”0001”,”1”,”0”
উদাহরণ
এর জন্য কোড হবে −
const arr = ["10", "0001", "111001", "1", "0"];
const m = 5, n = 3;
const findAllStrings = (arr = [], m = 1, n = 1) => {
const getCount = str => str.split('').reduce((acc, cur) => {
cur === '0' ? acc.zeros++ : acc.ones++;
return acc;
}, {zeros:0, ones:0});
const dp = Array.from({length: m+1}, () => Array(n+1).fill(0));
for(let i = 0; i < arr.length; i++) {
const {zeros, ones} = getCount(arr[i]);
for(let j = m; j >= zeros; j--) {
for(let k = n; k >= ones; k--) {
dp[j][k] = Math.max(dp[j-zeros][k-ones]+1, dp[j][k]);
}
}
}
return dp[m][n]
};
console.log(findAllStrings(arr, m, n)); আউটপুট
এবং কনসোলে আউটপুট হবে −
4
