The largest number not exceeding N and not containing any number in S

The challenge of finding the largest number not exceeding a given number N and not containing any of the digits in a string S is a problem that involves string manipulation and number theory. The goal is to determine the greatest possible number that is less than or equal to N while also excluding all of the digits found in the string S.

For example, consider a scenario where N equals 1000 and S equals "42". In this case, the largest number that does not exceed N and does not contain any digits in S is 999. This is because 999 is the largest possible number formed using the digits 0, 1, 3, 5, 6, 7, 8 and 9, excluding the digits 4 and 2 in the string S.

Different approaches can be used to solve this problem, such as iterating through all numbers up to N and verifying if their digits are not present in S, or by utilizing more complex methods like dynamic programming or backtracking.

Algorithm

Step 1 − We will declare two string variables named ‘N’ and ‘S’ in the main() function.

Step 2 - We will pass these two variables as parameters to the LargestNumberFinder() function.

Step 3 − We will convert the string number N and S into integer implicitly to do mathematical operations such as comparison.

Step 4 - We will remove the leading 0's from the numbers stored in N either manually or by creating a function that will do the same thing every time.

Step 5 − Then, we will start comparing the digits of the both the strings and finding out which is the largest number formed not more than 'N' that doesn't contain any digit from string ' S'.

Approach 1: - Naïve Approach

The basic way to find the largest number in a given string using all the numbers in another string is as follows. The main function declares variables and calls the LargestNumberFinder function. This function takes two strings as input and checks every value less than N that has all the digits in string S. If the condition is met, the value is returned in string format. The attendance function is used to determine whether the value stored in 'i' is part of a string S while converting S to an integer data type. The input string is converted to an integer and a loop is used to evaluate the condition. The code outputs the maximum value of all numbers in a given string that is also present in another string.

Example

Example

This code is a solution that finds the largest number smaller than N (the input string converted to an integer) consisting of the digits in the string S. The code utilizes two functions, 'attendance' and 'LargestNumberFinder' to determine and return the largest number. The attendance function takes as input an integer 'i' and a string 's', checks if the value stored in 'i' is part of the string 's', and converts 's' to an integer data type. The LargestNumberFinder function takes two strings 'x' and 's' as input, converts 'x' to an integer, and then uses the attendance function to check all values ​​less than N and all numbers are in 's'. The main function declares the variable and calls the LargestNumberFinder function, which returns the largest number as a string.

#include <iostream>
#include <string>
#include <vector>

// function to check whether value stored in ‘i’ is part of string S while also converting S into integer data type.
bool attendance(int i, std::string s) {
   while (i) {
      int first_digit = i % 10;
      i /= 10;
      int t = std::stoi(s);
      bool found = false;
      while (t) {
         int second_digit = t % 10;
         t /= 10;
         if (second_digit == first_digit) {
            found = true;
            break;
         }
      }
      if (!found)
         return false;
   }
   return true;
}

// function to input two strings and check for each value less than N with all digits present in S.
std::string LargestNumberFinder(std::string x, std::string s) {
   int N = std::stoi(x);
   for (int i = N; i >= 1; i--) {
      if (attendance(i, s)) {
         return std::to_string(i);
      }
   }
   return "-1";
}

// main function to declare the variables and call the function.
int main() {
   std::string N = "100709";
   std::string S = "70";
   std::cout << LargestNumberFinder(N, S);
}

Output

77777

Method 2: Efficient method

For the solution to problem 2, which is to get the largest possible number by replacing the numbers of the given number string N with the numbers of the given string S, this is an efficient method. The method first checks if every number of N is present in S and replaces the first number found in S with the largest number in S that is not in N. The remaining numbers are then replaced with the largest number in S that is not in N. Leading zeros are then removed and the result is returned as the largest possible number. This method is more efficient than the previous method because it does not require the string to be sorted.

Example

Example

The code solves a problem of finding the greatest number that can be formed from a given string "N" by replacing a digit with the highest digit not present in the string "S". The code utilizes an efficient method to solve the problem. The LargestNumberFinder function takes two string inputs, "num" and "s", and returns the largest possible number. The vector "vis_s" is utilized to store the values ​​of string "s". The code first identifies the first digit of string "num" that is part of string "s". Then it swaps that digit with the highest digit not present in string "s". The code then finds the highest digit not found in string "s" and replaces the rest of the digits in string "num" with that digit. The leading zeros are removed from the final string, and if the string is empty, the function returns "0". The code outputs the result by calling the function with inputs "N" and " S".

#include <iostream>
#include <string>
#include <vector>

using namespace std;

// function to check for all values of String N with String S and replacing the digit if found same with the largest possible digit not present in S.
string LargestNumberFinder(string num, string s) {
   vector<bool> vis_s(10, false);
   for (int i = 0; i < (int)s.size(); i++) {
      vis_s[int(s[i]) - 48] = true;
   }
   int n = num.size();
   int in = -1;
   for (int i = 0; i < n; i++) {
      if (vis_s[(int)num[i] - '0']) {
         in = i;
         break;
      }
   }
   if (in == -1) {
      return num;
   }
   for (char dig = num[in]; dig >= '0'; dig--) {
      if (vis_s[(int)dig - '0'] == 0) {
         num[in] = dig;
         break;
      }
   }
   char LargestDig = '0';
   for (char dig = '9'; dig >= '0'; dig--) {
      if (vis_s[dig - '0'] == false) {
         LargestDig = dig;
         break;
      }
   }
   for (int i = in + 1; i < n; i++) {
      num[i] = LargestDig;
   }
   int Count = 0;
   for (int i = 0; i < n; i++) {
      if (num[i] == '0')
         Count++;
      else
         break;
   }
   num.erase(0, Count);
   if ((int)num.size() == 0)
      return "0";
   return num;
}
int main() {
   string N = "161516";
   string S = "756";
   cout << LargestNumberFinder(N, S);
   return 0;
}

Output

149999

结论

通过这篇文章，我们更接近理解这些问题背后的原因，并理解了这些概念，这些概念将帮助我们在之前提到的重大实际问题中使用这些基本概念。就像在我们的代码中，我们分别解决每个问题，然后像制作美丽的手工品一样将代码缝合在一起，同样，我们将使用这个概念，尝试逐个解决问题。我们通常会从朴素的方法开始，但通过敏锐的眼光和努力，我们会找到更高效的方法。谁知道在阅读完这篇文章后，你会找到更好、更高效的方法，并进一步简化解决方案。所以，让我们坚持我们的信念和对思维和编码的信任，同时告别。

The above is the detailed content of The largest number not exceeding N and not containing any number in S. For more information, please follow other related articles on the PHP Chinese website!