Search code examples
javaarraysalgorithmmathlcm

How to reach a common number by adding a number k, to an array of numbers arr[]?

I am stuck with an algorithm problem since days. If we have an array of numbers, lets say, arr[2,4,9] and a var k, lets say k=7.

Is there a common number possible which can be reached by adding k to each of the elements inside the arr[] ?

EDIT:

WHen i say common number i mean a number X=(nikarr[i]) where n is a positive integer which could be different for each i, k is a positive integer provided to us, arr is the array of numbers. So it is basically to find an n for which nikarr[i] = a common number for all i.

I had a hunch of using LCM concept here but was not able to figure out the algorithim all the way through. A lead will be highly appreciated.

Solution

  • If you can add multiples of k to each element, then each element of the array can take on a value of the form

    value := arr[i] + j * k

    for some integer value j. Thus, they can only obtain the same value if all elements are initially some multiple of k difference from each other.

    Alternatively, you can view this problem in terms of modular arithmetic. Only if all elements reduce to the same value modulo k will you be able to obtain a common value between them by adding multiples of k

    forall e in arr ->  e mod k == c; for some constant c