How to divide number into integer pieces that are each a multiple of n?
Solution 1
var number = 5000;
var n = 7;
var values = [];
while (number > 0 && n > 0) {
var a = Math.floor(number / n / 50) * 50;
number -= a;
n--;
values.push(a);
} // 700 700 700 700 700 750 750
Edit
You can alternate Math.floor
and Math.ceil
to obtain the desired result:
while (number > 0 && n > 0) {
if (a%2 == 0)
a = Math.floor(number / n / 50) * 50;
else
a = Math.ceil(number / n / 50) * 50;
number -= a;
n--;
values.push(a);
} // 700 750 700 750 700 700 700
Solution 2
// i - an integer multiple of k
// k - an integer
// n - a valid array length
// returns an array of length n containing integer multiples of k
// such that the elements sum to i and the array is sorted,
// contains the minimum number of unique elements necessary to
// satisfy the first condition, the elements chosen are the
// closest together that satisfy the first condition.
function f(i, k, n) {
var minNumber = (((i / k) / n) | 0) * k;
var maxNumber = minNumber + k;
var numMax = (i - (minNumber * n)) / k;
var nums = [];
for (var i = 0; i < n - numMax; ++i) {
nums[i] = minNumber;
}
for (var i = n - numMax; i < n; ++i) {
nums[i] = maxNumber;
}
return nums;
}
So your second example would be
f(5000, 50, 7)
which yields
[700,700,700,700,700,750,750]
Solution 3
Let a be your starting number, k - number of parts you want to divide to.
Suppose, that b = a/n.
Now you want to divide b into k close integer parts.
- Take k numbers, each equal to b/k (integer division).
- Add 1 to first b%k numbers.
- Multiply each number by n.
Example:
a = 5000, n = 50, k = 7.
b = 100
Starting series {14, 14, 14, 14, 14, 14, 14}
Add 1 to first 2 integers {15, 15, 14, 14, 14, 14, 14}.
Multiply by 50 {750, 750, 700, 700, 700, 700, 700}.
Solution 4
I see your problem as basically trying to divide a sum of money into near-equal bundles of bills of a certain denomination.
For example, dividing 10,000 dollars into 7 near-equal bundles of 50-dollar bills.
function getBundles(sum, denomination, count, shuffle)
{
var p = Math.floor(sum / denomination);
var q = Math.floor(p / count);
var r = p - q * count;
console.log(r + " of " + ((q + 1) * denomination)
+ " and " + (count - r) + " of " + (q * denomination));
var b = new Array(count);
for (var i = 0; i < count; i++) {
b[i] = (r > 0 && (!shuffle || Math.random() < .5 || count - i == r)
? (--r, q + 1) : q)
* denomination;
}
return b;
}
// Divide 10,000 dollars into 7 near-equal bundles of 50-dollar bills
var bundles = getBundles(10000, 50, 7, true);
console.log("bundles: " + bundles);
Output:
4 of 1450 and 3 of 1400
bundles: 1400,1450,1450,1400,1450,1400,1450
If the last argument shuffle
is true
, it distributes the extra amount randomly between the bundles.
Solution 5
Your problem is the same as dividing a number X
into N
integer pieces that are all within 1 of each other (just multiply everything by 50 after you've found the result). Doing this is easy - set all N
numbers to Floor(X/N)
, then add 1 to X mod N
of them.
scubasteve
Updated on June 13, 2022Comments
-
scubasteve almost 2 years
Had a hard time coming up with a concise title for this. I'm sure there are terms for what I want to accomplish and there is no doubt a common algorithm to accomplish what I'm after - I just don't know about them yet.
I need to break up a number into n pieces that are each a multiple of 50. The number is itself a multiple of 50. Here is an example: Divide 5,000 by 3 and end up with three numbers that are each multiples of 50:
- 1,650
- 1,700
- 1,650
I also would like to have the numbers distributed so that they flip back and forth, here is an example with more numbers to illustrate this: Divide 5,000 by 7 and end up with 7 numbers that are each multiples of 50:
- 700
- 750
- 700
- 750
- 700
- 700
- 700
Note that in the above example I'm not worried that the extra 50 is not centered in the series, that is I don't need to have something like this:
- 700
- 700
- 750 <--- note the '50s' are centered
- 700
- 750 <--- note the '50s' are centered
- 700
- 700
Hopefully I've asked this clearly enough that you understand what I want to accomplish.
Update: Here is the function I'll be using.
var number = 5000; var n = 7; var multiple = 50; var values = getIntDividedIntoMultiple(number, n, multiple) function getIntDividedIntoMultiple(dividend, divisor, multiple) { var values = []; while (dividend> 0 && divisor > 0) { var a = Math.round(dividend/ divisor / multiple) * multiple; dividend -= a; divisor--; values.push(a); } return values; }
-
scubasteve about 12 yearsNice examples, how would you extend it to toggle the round up and round down so that you have 700, 750, 700, 750, etc. ?
-
Tadeck about 12 yearsWrong language. At least it shows how much code you need to type in Java to do a simple thing ;) (no offense)
-
scubasteve about 12 yearsYes, that works well. I was just stepping through the code in the debugger and watching how it worked and I get it.
-
scubasteve about 12 yearsNice and clean, provided a JS example which wasn't needed but is appreciated.
-
scubasteve about 12 yearsNice to see a different approach, not exactly what I wanted as the 750 values are back loaded consecutively.
-
scubasteve about 12 yearsAt first it "wooosh!" over my head w/ the terminology but after playing with some code I see what you're saying now ;)
-
scubasteve about 12 yearsI wasn't saying it as a negative, was just commenting that the extra effort for a JS example was appreciated considering you first supplied a c example.
-
Azaz Khan almost 4 yearsmultiple is undefined