Maximum multiple of a number with all digits same
Last Updated :
07 Mar, 2024
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 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# 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 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 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
Time Complexity: O(Y)
Auxiliary Space: O(1)
Explore
DSA Fundamentals
Data Structures
Algorithms
Advanced
Interview Preparation
Practice Problem