Split number into equal parts or what's closest to that

Question

I have a random number and I would like to divide it into several parts (addends) with conditions that a part can not be more than 20 and the parts must be as close to each other as possible.

For example, if my random number is 41, addends should be 14, 14, 13. If random number is 60 addends should be 20, 20, 20. If random number is 21 addends should be 11 and 10 and so on.

My code is in Ruby (Rails) so I would most appreciate an answer which gives an efficient implementation of this in Ruby, though pseudo-code or other programming languages are welcome as well.

This is what I found for arrays but I really need to do this thing with numbers: "Splitting an array into equal parts in ruby"

Answer 1

You can use this cool one-liner. It should work dividing by any amount of pieces you want:

def split_into n, p
    [n/p + 1] * (n%p) + [n/p] * (p - n%p)
end

print (split_into 32, 3) # => [11, 11, 10]

It basically divides the number into equal parts and splits the remainder by the first ones (1 for each). That and the fact that you can multiply and add arrays together, like so:

[1] * 3     # => [1, 1, 1]
[1] + [2]   # => [1, 2]

EDIT: Considering the rule that each piece should be smaller than 20, you can calculate the ideal amount of pieces as suggested by @Cary Swoveland:

p = (n / 20.0).ceil

Answer 2

Code

Let n be the given number that is to be divided and m the maximum value of each component.

def doit(n,m)
  nbr_components = (n/(m.to_f)).ceil
  smaller, nbr_larger = n.divmod(nbr_components)
  { smaller=>nbr_components-nbr_larger, smaller+1=>nbr_larger }.
    delete_if { |_,v| v.zero? }
end

Fixnum#divmod is an oft-overlooked method with many uses.

Examples

(1..300).to_a.sample(15).sort.each { |n| puts "doit(#{n},20) = #{doit(n,20)}" }
doit(2,20)   = {2=>1}
doit(7,20)   = {7=>1}
doit(13,20)  = {13=>1}
doit(19,20)  = {19=>1}
doit(32,20)  = {16=>2}
doit(36,20)  = {18=>2}
doit(47,20)  = {15=>1, 16=>2}
doit(61,20)  = {15=>3, 16=>1}
doit(77,20)  = {19=>3, 20=>1}
doit(146,20) = {18=>6, 19=>2}
doit(149,20) = {18=>3, 19=>5}
doit(160,20) = {20=>8}
doit(199,20) = {19=>1, 20=>9}
doit(253,20) = {19=>7, 20=>6}
doit(275,20) = {19=>5, 20=>9}

doit(11_347_155, 20)
  #=> {19=>5, 20=>567353}
5*19 + 567353*20
  #=> 11347155

Explanation

Suppose:

n = 77
m = 20

The steps are as follows:

nbr_components = (n/(m.to_f)).ceil
  #=> (77/20.0).ceil
  #=> 3.85.ceil
  #=> 4 
smaller, nbr_larger = n.divmod(nbr_components)
  #=> 77.divmod(4) 
  #=> [19, 1] 
smaller
  #=> 19
nbr_larger
  #=> 1
h = { smaller=>nbr_components-nbr_larger, smaller+1=>nbr_larger }
  #=> {19=>3, 20=>1}
h.delete_if { |_,v| v.zero? }
  #=> {19=>3, 20=>1}

Answer 3

There isn't a built in function to do this.

I can write out the solution for you, but in general you should include your own attempt in StackOverflow questions. This type of problem seems like practice to learn the fundamentals of the ruby language. I recommend going through a Ruby textbook if you're not sure where to start.

def split_number_into_three(number) # i.e. number=32
  base = Array.new(3, (number / 3)) # i.e. base=[10,10,10]
  remainder = number % 3            # i.e. remainer=2
  return base if remainder.zero?
  while remainder > 0
    base.each_with_index do |num, idx|
      if remainder > 0
        base[idx] += 1
        remainder -= 1
      end
    end
  end
  base
end

Running this code:

irb(main):035:0> split_number_into_three(32)
=> [11, 11, 10]