We are given two integers N & K and a sequence of N non-negative integers a1 a2 ... aN. We want to divide these numbers into X groups such that the sum of numbers of each group does not exceed K. What is the minimum possible value of X?
Can anyone please describe the approach for this problem? Is it possible to solve this problem in O(N2) or O(NlogN) or O(N) complexity?
Writing $$$O(N^2)$$$ is enough. (as it includes both $$$O(NlogN)$$$ and $$$O(N)$$$)
Given an array of $$$N$$$ integers, is it possible to partition them into two subsets $$$S_1$$$ and $$$S_2$$$ such that the sum of the elements in $$$S_1$$$ equals the sum of the elements in $$$S_2$$$? This is a well-known NP-complete problem (https://en.wikipedia.org/wiki/Partition_problem), meaning that we highly doubt that a polynomial-time solution for it exists.
However, we can reduce this to your problem. Suppose we had a polynomial-time algorithm which solved your problem. Set $$$K=\sum a_i/2$$$, run your algorithm, then check if $$$X = 2$$$; this solves the partition problem in polynomial time.
Thus, if you have found a polynomial-time solution to your problem, then you would have also found a polynomial time solution for the partition problem, and solved one of the Millennium Problems.
So, yeah, I doubt an $$$\mathcal{O}(n^2)$$$ algorithm exists.
You lose some "hardness" with that reduction. The partition problem is only weakly NP-complete, meaning you can solve it in polynomial time to the sum of $$$a_1, \dots, a_n$$$. The problem here is in fact the Bin packing problem, which is strongly NP-complete.
Ahh I see. Sorry, I'm a bit rusty with this topic. Thanks for the correction!