Maximum multiple of a number with all digits same
Given two positive integers X and Y (1 ? Y ? 105), find the maximum positive multiple (say M) of X such that M is less than 10Y and all the digits in the decimal representation of M are equal.
Note: If no positive multiple exists that satisfies the conditions, return -1.
Examples:
Input: X = 1, Y = 6
Output: 999999
Explanation: 999999 is the largest integer which is a multiple of 1, has all the same digits and less than 106.Input: X = 12, Y = 7
Output: 888888
Explanation: 888888 is the largest multiple of 12 which have all digits same and is less than 107.Input: X = 25, Y = 10
Output: -1
Explanation: No positive integers M satisfy the conditions.
Approach:
To solve the problem follow the below idea:
The main idea is to consider all the numbers less than 10Y which have the same digits in decimal representation and check if the number is a multiple of X, from all such multiples, the maximum one as the result.
Step-by-step approach:
- Consider a function f(n, d) which denotes the remainder of the number with length n and all digits d when divided by X.
- Calculate f(n, d) for every {n, d}.
- Notice that f(n ? 1, d) is a prefix of f(n, d). So: f(n, d) = (f(n?1, d)*10 + d)%X
- Find the maximum value of n for which f(n, d) = 0.
- Choose the one with the maximum d among the ones with the maximum n.
Below is the implementation of the above approach.
C++
// C++ program for finding maximum multiple // of a number with all the digits same #include <bits/stdc++.h> using namespace std; // Function for calculating maximum // multiple of X less than 10^Y string maxMultiple( int X, int Y) { // f(n, d) -> d digit is repeated // n times (ddd....d) pair< int , int > res = { 0, 0 }; int number = 0; for ( int d = 1; d <= 9; ++d) { for ( int n = 1; n < Y; ++n) { number = (10 * number + d) % X; if (number == 0) res = max(res, { n, d }); } } // No such multiple exits so return -1 if (res.first == 0) return "-1" ; // Generating the multiple // from pair res string ans = "" ; for ( int i = 1; i <= res.first; i++) ans += (res.second + '0' ); return ans; } // Driver function int main() { int X = 12, Y = 7; // Function Call cout << maxMultiple(X, Y); return 0; } |
Java
// Java program for finding maximum // multiple of a number with all the digits same class Main { // Function for calculating maximum multiple of X less than 10^Y public static String maxMultiple( int X, int Y) { // f(n, d) -> d digit is repeated // n times (ddd....d) int res[] = { 0 , 0 }; int number = 0 ; for ( int d = 1 ; d <= 9 ; ++d) { for ( int n = 1 ; n < Y; ++n) { number = ( 10 * number + d) % X; if (number == 0 ) { // res = max(res, {n, d}); // doing max of res & {n,d} if (res[ 0 ] > n) { // no change } else if (res[ 0 ] == n) { if (res[ 1 ] >= d) { // no change } else { res[ 0 ] = n; res[ 1 ] = d; } } else { res[ 0 ] = n; res[ 1 ] = d; } } } } // No such multiple exits so return -1 if (res[ 0 ] == 0 ) return "-1" ; // Generating the multiple from pair res String ans = "" ; char c = '0' ; while (res[ 1 ] > 0 ) { c++; res[ 1 ]--; } for ( int i = 1 ; i <= res[ 0 ]; i++) { ans += c; } return ans; } // Driver function public static void main(String[] args) { int X = 12 , Y = 7 ; // Function Call System.out.println(maxMultiple(X, Y)); } } // This code is contributed by ajaymakavana. |
C#
// C# program for finding maximum // multiple of a number with all the digits same using System; class GFG { // Function for calculating maximum multiple of X less than 10^Y static string maxMultiple( int X, int Y) { // f(n, d) -> d digit is repeated // n times (ddd....d) int [] res = {0, 0}; int number = 0; for ( int d = 1; d <= 9; ++d) { for ( int n = 1; n < Y; ++n) { number = (10 * number + d) % X; if (number == 0) { // res = max(res, {n, d}); // doing max of res & {n,d} if (res[0] > n) { // no change } else if (res[0] == n) { if (res[1] >= d) { // no change } else { res[0] = n; res[1] = d; } } else { res[0] = n; res[1] = d; } } } } // No such multiple exits so return -1 if (res[0] == 0) return "-1" ; // Generating the multiple from pair res string ans = "" ; char c = '0' ; while (res[1] > 0) { c++; res[1]--; } for ( int i = 1; i <= res[0]; i++) { ans += c; } return ans; } // Driver function public static void Main(String[] args) { int X = 12, Y = 7; // Function Call Console.Write(maxMultiple(X, Y)); } } // This code is contributed by Aman Kumar. |
Javascript
// JavaScript program for finding maximum // multiple of a number with all the digits same // Function for calculating maximum // multiple of X less than 10^Y function maxMultiple(X, Y){ var res = [ 0, 0 ]; var number = 0; for (let d = 1; d <= 9; ++d) { for (let n = 1; n < Y; ++n) { number = (10 * number + d) % X; if (number == 0) { // res = max(res, {n, d}); // doing max of res & {n,d} if (res[0] > n) { // no change } else if (res[0] == n) { if (res[1] >= d) { // no change } else { res[0] = n; res[1] = d; } } else { res[0] = n; res[1] = d; } } } } // No such multiple exits so return -1 if (res[0] == 0) return "-1" ; // Generating the multiple from pair res var ans = "" ; var c = '0' ; while (res[1] > 0) { c++; res[1]--; } for (let i = 1; i <= res[0]; i++) { ans += c; } return ans; } var X = 12, Y = 7; // Function Call console.log(maxMultiple(X, Y)); // This code is contributed by lokeshmvs21. |
Python3
# Python3 program for finding maximum multiple # of a number with all the digits same # Function for calculating maximum # multiple of X less than 10^Y def maxMultiple(X, Y) : # f(n, d) -> d digit is repeated # n times (ddd....d) res = ( 0 , 0 ); number = 0 ; for d in range ( 1 , 10 ) : for n in range ( 1 , Y) : number = ( 10 * number + d) % X; if (number = = 0 ) : res = max (res, ( n, d )); # No such multiple exits so return -1 if (res[ 0 ] = = 0 ) : return "-1" ; # Generating the multiple # from pair res ans = ""; for i in range ( 1 , res[ 0 ] + 1 ) : ans + = str (res[ 1 ]); return ans; # Driver function if __name__ = = "__main__" : X = 12 ; Y = 7 ; # Function Call print (maxMultiple(X, Y)); # This code is contributed by AnkThon |
888888
Time Complexity: O(Y)
Auxiliary Space: O(1)
Contact Us