Maximum multiple of a number with all digits same - Coding

Given two positive integers X and Y (1 ? Y ? 10⁵), find the maximum positive multiple (say M) of X such that M is less than 10^Y 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 10⁶.

Input: X = 12, Y = 7
Output: 888888
Explanation: 888888 is the largest multiple of 12 which have all digits same and is less than 10⁷.

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 10^Y 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

Output

Time Complexity: O(Y)
Auxiliary Space: O(1)

Reffered: https://www.geeksforgeeks.org

Mathematical

Related
Check if given vectors are Parallel or Perpendicular?
Maximize the money when no two adjacent Array indices can be chosen
12 hour clock Multiplication
Count ways to form Triplet of consecutive integers having the given numbers
Remainder Evaluation

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	17