C++程序查找使得其与数组每个元素取模结果都相同的‘k’


在这篇文章中,我们将讨论一个程序,用于查找一个整数‘k’,使得它与给定数组的每个元素取模的结果都相同。

例如,假设我们得到了一个数组,

arr = {12, 22, 32}

那么我们得到k的输出值为1、2、5、10。

以数组中两个值‘x’和‘y’(x>y)为例。那么我们有(y+差值)%k = y%k。求解得到,

difference%k = 0

因此,我们将找到数组中最大元素和最小元素之差的所有约数,然后检查每个约数是否对数组中的每个元素都具有相同的余数。

示例

 在线演示

#include<bits/stdc++.h>
using namespace std;
int equal_modulus (int arr[], int len) {
   sort(arr, arr + len);
   int diff = arr[len-1] - arr[0];
   //vector to store all the divisors
   vector <int> divi;
   for (int i = 1; i*i <= diff; i++) {
      if (diff%i == 0) {
         divi.push_back(i);
         if (i != diff/i)
            divi.push_back(diff/i);
      }
   }
   //to check if remainder is equal for every element
   for (int i = 0; i < divi.size(); i++) {
      int temp = arr[0]%divi[i];
      int j;
      for (j = 1; j < len; j++)
         if (arr[j] % divi[i] != temp)
            break;
      //to print the values of k
      if (j == len)
         cout << divi[i] <<" ";
   }
   return 0;
}
int main() {
   int arr[] = {12, 22, 32};
   int len = sizeof(arr)/sizeof(arr[0]);
   cout << "The values of K :" << endl;
   equal_modulus(arr, len);
   return 0;
}

输出

The values of K :
1 2 10 5

更新于: 2019年10月3日

271 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告