Repeating unit divisibility (using C++)

In this article, we will discuss finding the number of repeating units that is divisible by N. A repeating unit is simply the number of repeats of 1, let R(k) be the repeating unit, where k is the length of 1. For example, R(4) = 1111. So we need to find the minimum number of k that R(k) is divisible by N, for example -

Input : N = 13
Output : k = 6
Explanation : R(6) i.e 111111 is divisible by 13.

Input : N = 31
Output : k = 15

Methods to find the solution

You can do this by checking each of k starting from 1 value to solve this problem, where R(k) is divisible by N. But using this solution we won't be able to determine whether N is divisible by any value of R(k). This will make the program too complex and may not even work.

An efficient way to solve this program is,

• Check whether N is relatively prime with 10.
• If not, then R(k) is not divisible by N for any value of k.
• If yes, then for each repeating unit R(1), R(2), R(3)...etc., calculate the remainder of dividing R(i) by N, so the remainder is n.
• Find the same remainder of R(i) and R(j), where R(i) and R(j) are two repeating units such that R(i) - R(j) is divisible by N .
• aThe difference between R(i) and R(j) will be repeated units multiplied by some power of 10, but 10 and N are relatively prime, so R(k) will be divisible by N.

Example

#include <bits/stdc++.h>
using namespace std;

int main() {
   int N = 31;
   int k = 1;
   // checking if N is coprime with 10.
   if (N % 2 == 0 || N % 5 == 0){
      k = 0;
   } else {
      int r = 1;
      int power = 1;
      // check until the remainder is divisible by N.
      while (r % N != 0) {
         k++;
         power = power * 10 % N;
         r = (r + power) % N;
      }
   }
   cout << "Value for k : "<< k;
   return 0;
}

Output

Value for k : 15

Conclusion

In this article, we discuss finding the k value of R(k), where R( k) is a repeating unit divisible by a given N. We discussed an optimistic approach to finding the value of k. We also discussed C code to solve this problem. You can write this code in any other language like Java, C, Python, etc. We hope this article was helpful to you.

The above is the detailed content of Repeating unit divisibility (using C++). For more information, please follow other related articles on the PHP Chinese website!