Home > Backend Development > C++ > Repeating unit divisibility (using C++)

Repeating unit divisibility (using C++)

王林
Release: 2023-08-26 22:37:12
forward
1458 people have browsed it

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
Copy after login

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;
}

Copy after login

Output

Value for k : 15
Copy after login

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!

source:tutorialspoint.com
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template