Largest number less than N whose each digit is prime number in Java
In this tutorial, we are going to find Largest number less than N whose each digit is prime number in Java. Provided an extremely large number, denoted by N, with a minimum of 1 and a maximum of 105 digits. Our goal is to find the largest number named X, which is smaller than N and that satisfies the condition that each of the digits of X be a prime number. In other words, the objective is to determine the largest number that is still smaller than the given number N and can be obtained entirely using prime numbers. Let’s see a few examples to understand it.
Example 1:
Input: N = 1110
Output: 777
Explanation: As we can see, 777 is the largest number, less than 1110, where every single digit is a prime number.
Example 2:
Input: N = 17
Output: 7
Explanation: 7 is the largest number which is a prime number and is less than 17. Hence is no other prime largest 7 and smaller than 17.
Approach 1: Using Prime Digit Maximization
Follow the below steps to solve the problem.
Step 1: Create an empty array called ansr for storing results, an integer variable numbStr for the current position, and an integer variable flag for obtaining a smaller prime digit.
Step 2: Define two arrays named prm: to determine whether a digit is prime or not and largestPrime, which contains the largest prime digit that is less than or equal to each digit (0–9).
Step 3: Determine whether the given number has only one digit. If yes, assign the largest prime digit that is less than or equal to the provided digit to the result array ansr.
Step 4: If the given number begins with the digit 1, fill the result array with 7s because 7 is the largest prime digit.
Step 5: Iterate through the digits in the numb array:
Step 5.1: if the current digit is a prime number, add the digit to the array named ansr.
Step 5.2: If not a prime:
Step 5.2.1: Find the largest prime digit less than it and add it to the result array ansr.
Step 5.3: If the given number is a prime, assign the largest prime digit that is less than or equal to the last digit to the result array.
Step 5.4: If no smaller prime digits were determined, modify the last digit as required.
Step 6: Fill the remaining digits of the result array ansr with 7s.
Step 7: Return the result array, ansr.
FileName: LargestNumbFormedWithPrimeNumber.java
// importing io packages import java.io.*; public class LargestNumbFormedWithPrimeNumber { // method to generate the largest number composed of prime digits less than numb static char[] PrimeDgtNumbr(char numb[], int len) { char[] ansr = new char[len]; int numbStr = 0; // to track if a smaller prime digit has been found int flag = 0; int i; // array indicating whether a digit is prime or not, i.e., 1 for prime int prm[] = { 0, 0, 1, 1, 0, 1, 0, 1, 0, 0 }; // an array which contains the largest prime digit that is less than or equal to each digit int largestPrime[] = { 0, 0, 0, 2, 3, 3, 5, 5, 7, 7 }; // the case where numb has only one digit if (len == 1) { ansr[0] = (char)(largestPrime[numb[0] - '0'] + '0'); // assign the largest prime digit less than or equal to the given digit ansr[1] = '