Given three integers X, N and M. The task is to find XXX…(N times) % M where X can be any digit from the range [1, 9].
Examples:
Input: X = 7, N = 7, M = 50
Output: 27
7777777 % 50 = 27Input: X = 1, N = 10, M = 9
Output: 1
1111111111 % 9 = 1
Approach: The problem can be solved using Divide and Conquer technique. The modulo of smaller numbers like X, XX, XXX etc. can be easily calculated. But problem arises for larger numbers. Hence, the number can be split as follows:
- If N is even -> XXX…(N times) = (XXX…(N/2 times) * 10N/2) + XXX..(N/2 times).
- If N is odd -> XXX…(N times) = (XXX…(N/2 times) * 10(N/2)+1) + (XXX…(N/2 times) * 10) + X.
By using the above formula, the number is divided into smaller parts whose modular operation can be easily found. Using the property (a + b) % m = (a % m + b % m) % m, a recursive divide and conquer solution is made to find the modulo of larger number using results of smaller numbers.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Iterative function to calculate// (x ^ y) % p in O(log y)int power(int x, unsigned int y, int p){ // Initialize result int res = 1; // Update x if it is >= p x = x % p; while (y > 0) { // If y is odd, multiply x with result if (y & 1) res = (res * x) % p; // y must be even now // y = y / 2 y = y >> 1; x = (x * x) % p; } return res;}// Function to return XXX.....(N times) % Mint findModuloByM(int X, int N, int M){ // Return the mod by M of smaller numbers if (N < 6) { // Creating a string of N X's string temp(N, (char)(48 + X)); // Converting the string to int // and calculating the modulo int res = stoi(temp) % M; return res; } // Checking the parity of N if (N % 2 == 0) { // Dividing the number into equal half int half = findModuloByM(X, N / 2, M) % M; // Utilizing the formula for even N int res = (half * power(10, N / 2, M) + half) % M; return res; } else { // Dividing the number into equal half int half = findModuloByM(X, N / 2, M) % M; // Utilizing the formula for odd N int res = (half * power(10, N / 2 + 1, M) + half * 10 + X) % M; return res; }}// Driver codeint main(){ int X = 6, N = 14, M = 9; // Print XXX...(N times) % M cout << findModuloByM(X, N, M); return 0;} |
Java
// Java implementation of the approachclass GFG{ // Iterative function to calculate // (x ^ y) % p in O(log y) static int power(int x, int y, int p) { // Initialize result int res = 1; // Update x if it is >= p x = x % p; while (y > 0) { // If y is odd, multiply x with result if (y % 2 == 1) res = (res * x) % p; // y must be even now // y = y / 2 y = y >> 1; x = (x * x) % p; } return res; } // Function to return XXX.....(N times) % M static int findModuloByM(int X, int N, int M) { // Return the mod by M of smaller numbers if (N < 6) { // Creating a string of N X's String temp=""; for(int i = 0; i< N ; i++) temp = temp + (char)(X + 48); // Converting the string to int // and calculating the modulo int res = Integer.parseInt(temp) % M; return res; } // Checking the parity of N if (N % 2 == 0) { // Dividing the number into equal half int half = findModuloByM(X, N / 2, M) % M; // Utilizing the formula for even N int res = (half * power(10, N / 2, M) + half) % M; return res; } else { // Dividing the number into equal half int half = findModuloByM(X, N / 2, M) % M; // Utilizing the formula for odd N int res = (half * power(10, N / 2 + 1, M) + half * 10 + X) % M; return res; } } // Driver code public static void main (String[] args) { int X = 6, N = 14, M = 9; // Print XXX...(N times) % M System.out.println(findModuloByM(X, N, M)); }} // This code is contributed by ihritik |
Python3
# Python3 implementation of the above approach # Iterative function to calculate # (x ^ y) % p in O(log y) def power(x, y, p) : # Initialize result res = 1; # Update x if it is >= p x = x % p; while (y > 0) : # If y is odd, multiply x with result if (y and 1) : res = (res * x) % p; # y must be even now # y = y // 2 y = y >> 1; x = (x * x) % p; return res; # Function to return XXX.....(N times) % M def findModuloByM(X, N, M) : # Return the mod by M of smaller numbers if (N < 6) : # Creating a string of N X's temp = chr(48 + X) * N # Converting the string to int # and calculating the modulo res = int(temp) % M; return res; # Checking the parity of N if (N % 2 == 0) : # Dividing the number into equal half half = findModuloByM(X, N // 2, M) % M; # Utilizing the formula for even N res = (half * power(10, N // 2, M) + half) % M; return res; else : # Dividing the number into equal half half = findModuloByM(X, N // 2, M) % M; # Utilizing the formula for odd N res = (half * power(10, N // 2 + 1, M) + half * 10 + X) % M; return res; # Driver code if __name__ == "__main__" : X = 6; N = 14; M = 9; # Print XXX...(N times) % M print(findModuloByM(X, N, M)); # This code is contributed by Ryuga |
C#
// C# implementation of the approachusing System;class GFG{ // Iterative function to calculate // (x ^ y) % p in O(log y) static int power(int x, int y, int p) { // Initialize result int res = 1; // Update x if it is >= p x = x % p; while (y > 0) { // If y is odd, multiply x with result if (y % 2 == 1) res = (res * x) % p; // y must be even now // y = y / 2 y = y >> 1; x = (x * x) % p; } return res; } // Function to return XXX.....(N times) % M static int findModuloByM(int X, int N, int M) { // Return the mod by M of smaller numbers if (N < 6) { // Creating a string of N X's string temp=""; for(int i = 0; i< N ; i++) temp = temp + (char)(X + 48); // Converting the string to int // and calculating the modulo int res = Convert.ToInt32(temp) % M; return res; } // Checking the parity of N if (N % 2 == 0) { // Dividing the number into equal half int half = findModuloByM(X, N / 2, M) % M; // Utilizing the formula for even N int res = (half * power(10, N / 2, M) + half) % M; return res; } else { // Dividing the number into equal half int half = findModuloByM(X, N / 2, M) % M; // Utilizing the formula for odd N int res = (half * power(10, N / 2 + 1, M) + half * 10 + X) % M; return res; } } // Driver code public static void Main () { int X = 6, N = 14, M = 9; // Print XXX...(N times) % M Console.WriteLine(findModuloByM(X, N, M)); }} // This code is contributed by ihritik |
PHP
<?php// PHP implementation of the above approach // Iterative function to calculate // (x ^ y) % p in O(log y) function power($x, $y, $p) { // Initialize result $res = 1; // Update x if it is >= p $x = $x % $p; while ($y > 0) { // If y is odd, multiply x with result if ($y&1) $res = ($res * $x) % $p; // y must be even now // y = y // 2 $y = $y >> 1; $x = ($x * $x) % $p; } return $res; }// Function to return XXX.....(N times) % M function findModuloByM($X, $N, $M){ // Return the mod by M of smaller numbers if ($N < 6) { // Creating a string of N X's $temp = chr(48 + $X) * $N; // Converting the string to int // and calculating the modulo $res = intval($temp) % $M; return $res; } // Checking the parity of N if ($N % 2 == 0) { // Dividing the number into equal half $half = findModuloByM($X, (int)($N / 2), $M) % $M; // Utilizing the formula for even N $res = ($half * power(10,(int)($N / 2), $M) + $half) % $M; return $res; } else { // Dividing the number into equal half $half = findModuloByM($X, (int)($N / 2), $M) % $M; // Utilizing the formula for odd N $res = ($half * power(10, (int)($N / 2) + 1, $M) + $half * 10 + $X) % $M; return $res; }}// Driver code $X = 6; $N = 14; $M = 9; // Print XXX...(N times) % M print(findModuloByM($X, $N, $M)); // This code is contributed by mits?> |
Javascript
<script>// Javascript implementation of the approach// Iterative function to calculate// (x ^ y) % p in O(log y)function power(x, y, p){ // Initialize result var res = 1; // Update x if it is >= p x = x % p; while (y > 0) { // If y is odd, multiply x with result if (y & 1) res = (res * x) % p; // y must be even now // y = y / 2 y = y >> 1; x = (x * x) % p; } return res;}// Function to return XXX.....(N times) % Mfunction findModuloByM(X, N, M){ // Return the mod by M of smaller numbers if (N < 6) { var temp = ""; // Creating a string of N X's for(var i = 1; i < N; i++) { temp += String.fromCharCode(48 + X); } // Converting the string to int // and calculating the modulo var res = parseInt(temp) % M; return res; } // Checking the parity of N if (N % 2 == 0) { // Dividing the number into equal half var half = findModuloByM(X, N / 2, M) % M; // Utilizing the formula for even N var res = (half * power(10, N / 2, M) + half) % M; return res; } else { // Dividing the number into equal half var half = findModuloByM(X, N / 2, M) % M; // Utilizing the formula for odd N var res = (half * power(10, N / 2 + 1, M) + half * 10 + X) % M; return res; }}// Driver codevar X = 6, N = 14, M = 9;// Print XXX...(N times) % Mdocument.write( findModuloByM(X, N, M));// This code is contributed by noob2000</script> |
Output:
3
Time Complexity : O(log(N))
Space Complexity : O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
