CODEWITHSUNDEEP
algorithm
rAzOr
rAzOr

Reputation: 320

Finding nearest next number for n, with sum of multiple of 2 numbers

For a given number n, find difference between next nearest number that can be formed with multiples of two given numbers(a,b) and n.

Example:
    n = 49, (a, b) = (13, 17) => Difference = 2
    Nearest number would be = 51 (3*17, 0*13)

    n = 16, (a, b) = (2 , 5) => Difference = 0
    Nearest number would be = 16 (2*5, 3*2)

    n = 25, (a, b) = (13, 17) => Difference = 1
    Nearest number would be = 26 (0*17, 2*13)

How do I go about this problem?

What I have written is: (In ruby)

def find_next_num_diff(x,y,z)
  x, y = x > y ? [x, y] : [y, x]
  while(z%y > 0 && z >= x) do
    z -= x
  end
  if z%y == 0
    return 0
  else
    return [y-(z%y), x-z].min
  end
end

The above code won't work for last kind of examples.

Edit: No negative numbers. And only sum. At first I thought of this problem as solving for X & Y for Equation Xa + Yb >= n and X, Y > 0

Upvotes: 0

Views: 119

Answers (2)

spickermann
spickermann

Reputation: 106932

I would start with something like this:

def find_next_num_diff(n, a, b)
  multiples_of_a = (0..n+a-1).step(a).to_a
  multiples_of_b = (0..n+b-1).step(b).to_a

  multiples_of_a.product(multiples_of_b).map { |x, y| (n - (x + y)).abs }.min
end

find_next_num_diff(49, 13, 17)
#=> 2
find_next_num_diff(16, 2, 5)
#=> 0
find_next_num_diff(25, 13, 17)
#=> 1

Or you might want to use the following implementation that needs less memory, because it doesn't store the cartesian product in memory:

def find_next_num_diff(n, a, b)
  a_multiples = (0..n+a-1).step(a)
  b_multiples = (0..n+b-1).step(b)

  smallest = Float::INFINITY

  a_multiples.each do |x|
    b_multiples.each do |y|
      smallest = [smallest, (n - (x + y)).abs].min
    end
  end

  smallest
end

Upvotes: 1

Tagc
Tagc

Reputation: 9076

I'm quite confident it's a very inefficient solution but here's one that I believe works. It uses recursion with a branching factor of 2:

def recurse(a_base, b_base, a_mult, b_mult, n):
    a = a_base * a_mult
    b = b_base * b_mult

    if a + b >= n:
        return (a + b) - n, a_mult, b_mult
    else:
        diff_1, a_mult_1, b_mult_1 = recurse(a_base, b_base, a_mult + 1, b_mult, n)
        diff_2, a_mult_2, b_mult_2 = recurse(a_base, b_base, a_mult, b_mult + 1, n)

        if diff_1 <= diff_2:
            return diff_1, a_mult_1, b_mult_1
        else:
            return diff_2, a_mult_2, b_mult_2


def find_next_num_diff(a, b, n):
    return recurse(a, b, 0, 0, n)


if __name__ == '__main__':
    print(find_next_num_diff(13, 17, 49))
    print(find_next_num_diff(2, 5, 16))
    print(find_next_num_diff(13, 17, 25))

Output

# Smallest diff, multiple of a, multiple of b
(2, 0, 3)
(0, 8, 0)
(1, 2, 0)

For convenience, here's the examples in your post to compare against:

n = 49, (a, b) = (13, 17) => Difference = 2
Nearest number would be = 51 (3*17, 0*13)

n = 16, (a, b) = (2 , 5) => Difference = 0
Nearest number would be = 16 (2*5, 3*2)

n = 25, (a, b) = (13, 17) => Difference = 1
Nearest number would be = 26 (0*17, 2*13)

Notice that my solution yielded a different combination of multiples for the second example, but that the diff is still 0.

Upvotes: 0

Related Questions