CODEWITHSUNDEEP
algorithmmath
anilonwebs
anilonwebs

Reputation: 661

Algorithm for Combinational Values

I was trying to write an algorithm for given problem:

we are given a set of numbers- {n1,n2,n3,n4,n5......} and we have to check that can we derive a number(Say X) using addition and subtraction by given numbers. X will always be less than all elements of the given set.

Eg.

Set: {2,3,4,6,9}
given number: 1, Result: Yes
9-4-4 =1

Set: {3,4,6,9}
given number: 2, Result: Yes
6-4 = 2

Thanks in advance.

Upvotes: 0

Views: 130

Answers (2)

Alin P.
Alin P.

Reputation: 44346

Assuming, from your first example, that you can use a number multiple times.

The given number must be a multiple of the GCD of your set. That is the only condition. It doesn't matter how big it is.

If you only want an Yes/No answer then it is sufficient to find the GCD. If you also want an expression for the given number the problem can be replaced with finding an expression for the GCD.

GCD = X+Y+..+Z-T-U-...-V

Upvotes: 0

Sven Marnach
Sven Marnach

Reputation: 601391

Effectively you are looking for the ideal generated by the numbers in your set. The intergers form a principal ideal domain, which means every ideal is generated by a single integer. All you have to do is find this single integer -- say g -- and check whether X can be devided by g. Finding g is also easy -- it's the greatest common divisor of all elements in your set, which can be found using the Euclidean algorithm.

You example sets can generate every integer by addition and substraction, since the can generate 1. For example for the set {3,4,6,9} you have 1=4-3, and any integer n can be written as n times the sum of 4-3.

Upvotes: 3

Related Questions