সমস্যা
আমাদের একটি জাভাস্ক্রিপ্ট ফাংশন লিখতে হবে যা একটি নন-নেগেটিভ ইন্টিজার অ্যারে arr প্রথম আর্গুমেন্ট এবং একটি ইন্টিজার num (num < arr.length) دومা আর্গুমেন্ট হিসেবে নেবে।
ফাংশনটির কাজ হলো অ্যারেটিকে num টি নন-এম্পটি ক্রমাগত সাবঅ্যারেতে ভাগ করা। ভাগ করা হবে এমনভাবে যাতে এই সাবঅ্যারেগুলোর মধ্যে সর্বোচ্চ যোগফলটি ন্যূনতম হয়। ফাংশনটি সেই ন্যূনতম সম্ভব সর্বোচ্চ যোগফলটি রিটার্ন করবে।
উদাহরণ:
const arr = [5, 1, 4, 8, 7]; const num = 2;
আউটপুট হবে:
const output = 15;
আউটপুট ব্যাখ্যা:
যদিও অ্যারেকে ৪ভাবে ভাগ করা যায়, কিন্তু [5, 1, 4] এবং [8, 7] এই দুটি গ্রুপে ভাগ করলে তাদের যোগফল যথাক্রমে ১০ ও ১৫। সর্বোচ্চ যোগফল ১৫ যা সম্ভব ন্যূনতম।
উদাহরণ
কোডটি নিচের মতো (বাইনারি সার্চ অন আনসার):
const arr = [5, 1, 4, 8, 7]; const num = 2; const splitArray = (arr = [], num = 1) => { let max = 0; let sum = 0; const split = (arr, mid) => { let part = 1; let tempSum = 0; for (let num of arr) { if (tempSum + num > mid) { tempSum = num; part++; } else { tempSum += num; } } return part; }; for (let num of arr) { max = Math.max(max, num); sum += num; }; let low = max; let high = sum; while (low < high) { let mid = Math.floor((high+low)/2); let part = split(arr, mid); if (part > num) { low = mid + 1; } else { high = mid; } } return low; }; console.log(splitArray(arr, num)); কোড ব্যাখ্যা:
বাইনারি সার্চ ব্যবহার করে চেক করা হয়েছে কোনো নির্দিষ্ট ম্যাক্সিমাম সাম লিমিটে কি num টি সাবঅ্যারে বানানো সম্ভব।
আউটপুট
কনসোলে আউটপুট:
15
