0
$\begingroup$

We are provided with a positive number N which denotes that we have N objects . Each of those N objects hold a value. Now we are provided a task to add non-negative value to the objects in such a way that the resultant values of N objects have a common factor .
Find the minimum sum of all the numbers added.

For example :- Suppose N = 3 and we have objects with values as:-
11 ,21 ,24
The answer to this is 1 as we can add 1 to 11 , and thus resultant values become
12, 21, 24 ,
which have 3 as common factor .

$\endgroup$
  • $\begingroup$ I understand that you can add a number (same number) to all the objects that you want. In that case, if you have $N$ objects, all even, then sum 0. If this isn't the case, plus 1 to all the odd objects and then the resulting $N$ objects are all even. Could you be more clear? $\endgroup$ – sinbadh Jan 1 '16 at 12:41
  • $\begingroup$ The thing is not about odd or even . How can your technique work for the example i mentioned above? $\endgroup$ – user249117 Jan 1 '16 at 12:45
  • $\begingroup$ Is the common factor specified? If not, then the comment of @sinbadh seems to settle the matter. In your example, add $1$ to $11,21$ to get the triple $12,22,24$ which share the factor $2$. On its face, that would seem to pass your requirements... $\endgroup$ – lulu Jan 1 '16 at 12:48
  • $\begingroup$ @lulu but that would not be the minimum, the question clearly asks for minimum. $\endgroup$ – Daga Jan 1 '16 at 12:49
  • $\begingroup$ But minimum such value is required . Common factor is required , and min value is 1 , whereas as per the above mentioned procedure , answer is 2 $\endgroup$ – user249117 Jan 1 '16 at 12:50
0
$\begingroup$

Thinking the problem as a programming question will make it easy.

For given $N$ objects $\{x_1,x_2,x_3,\dots,x_n\}$, find all values of primes $p$, such that there exist a value of $i$, such that $x_i \mod p =0 $.

For all such values of $p$ find the minimum value to be added to $x_i$, such that $x_i \mod p =0 $ if $x_i \mod p \ne 0 $. This value is equal to $p - (x_i \mod p) $.

For all values of p, find the sum of all the values added to $x_i$, the minimum among them will be the answer.

$\endgroup$
  • $\begingroup$ Thanx a lot . This was the exact approach i was looking for $\endgroup$ – user249117 Jan 1 '16 at 13:21
1
$\begingroup$

Don't see a simple closed formula. As a programming method, note that the even/odd calculation gives an upper bound (equal to the number of odd numbers in the list). Then work prime by prime until the least element needs too great a summand.

Example (randomly chosen): $$L=\{12,17,23,31,43,57,91,102\}$$

There are $6$ odd numbers in the list so the upper bound is $6$.

Now try $p=3$ working mod$3$ we get $$L\equiv \{0,2,2,1,1,0,1,0\}$$. Thus we must add $\{0,1,1,2,2,0,2,0\}$ which sums to a value greater than $6$.

Now try $p=5$. working mod$5$ we get $$L\equiv \{2,2,3,1,3,2,1,2\}$$ and again it is no good.

Similarly, we can rule out $p=\{7,11,13,17\}$. No need to look any further as we we'd clearly have to add more than $6$ to $12$. Hence the upper bound was good, and the answer is $6$.

$\endgroup$
  • $\begingroup$ Thanx a lot . That helped a lot :) $\endgroup$ – user249117 Jan 1 '16 at 13:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.