Home >Backend Development >C++ >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
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,
#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; }
Value for k : 15
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!