Finding K Such That Its Modulus With Each Array Element Is Same in C++

In this tutorial, we are going to write a program that finds a number such that its modulus with each array element is same. Let's see an example.

Input − arr = {10, 4, 2}

Output − 1 2

If there are two numbers x, y and x > y, assume that x - y = d.

Then the x = y + d.

Let's say we have a number k such that x?%k = y%k. Apply modulo k for the above equation and find the value d.

x%k = (y+d)%k
y%k = y%k +d%k
d%k = 0

From the above calculation, if the number k is the divisor of the difference between the x and y. Then it will be a divisor of the numbers x and y.

Let's apply the same concept to the array of elements. And find the k value. See the steps to solve the problem.

• Initialize the array with numbers

• Here, the d will be the difference between the max and min values of the array elements.

• Sort the values of the array using sort method.

• Find the difference between the last and first numbers.

• If the difference is zero, then all the numbers are same. Then the result of module with any number gives the same result.

• Else find the divisors of the number d. And store them.

• Iterate over all the divisors and find number whose modulo with all the array elements are same.

Example

Let's see the code.

 Live Demo

#include <bits/stdc++.h>
using namespace std;
void findNumbers(int arr[], int n) {
   sort(arr, arr + n);
   int d = arr[n - 1] - arr[0];
   // check whether all elements are same or not
   if (d == 0) {
      cout << "Infinite number of k's";
      return;
   }
   // finding the divisors of d
   vector <int> v;
   for (int i = 1; i * i <= d; i++) {
      if (d % i == 0) {
         v.push_back(i);
         if (i != d / i) {
            v.push_back(d / i);
         }
      }
   }
   // findind the k's
   for (int i = 0; i < v.size(); i++) {
      int temp = arr[0] % v[i];
      int j;
      for (j = 1; j < n; j++) {
         if (arr[j] % v[i] != temp) {
            break;
         }
      }
      if (j == n)
         cout << v[i] << " ";
      }
      cout << endl;
   }
   int main() {
      int arr[] = {10, 4, 2};
      findNumbers(arr, 3);
   return 0;
}

Output

If you run the above code, then you will get the following result.

1 2

Conclusion

If you have any queries in the tutorial, mention them in the comment section.