Given an integer n, find the largest digit present in it.
Example 1
Input: n = 58241
Output: 8
Explanation: The digits are 5, 8, 2, 4, 1, and the largest among them is 8.
Example 2
Input: n = 70039
Output: 9
Explanation: The digits are 7, 0, 0, 3, 9, and the largest among them is 9.
Approach
To find the largest digit, every digit must be checked once. So the main question is: how can digits be taken out from a number one by one?
A useful property helps here. The last digit of a number can be found using n % 10. For example, 58241 % 10 gives 1, so the last digit becomes easy to access. After checking that digit, it should be removed so the next digit can be processed. That is why integer division by 10 is used.
So the idea becomes simple. Take the last digit, compare it with the largest digit found so far, remove it from the number, and continue the same process. In this way, all digits get checked, and the biggest one is saved as the answer.
Algorithm
First, make the number positive by taking its absolute value. This is done because only the digits matter here, not the minus sign. If the number is
0, return0immediately because0itself is the only digit present.Keep a variable
largestto store the biggest digit found so far. In the beginning, set it to0so every digit in the number can be compared with it.Take the last digit using
n % 10. This gives one digit from the number that can now be checked. Compare it withlargest, and if this digit is bigger, updatelargest.Remove the last digit using integer division by
10. This helps move to the remaining digits of the number so the same process can continue.Repeat this until the number becomes
0. After all digits are checked, returnlargestas the answer.
Key Points
If
largestever becomes9, the process can stop early because no digit can be larger than9.If the number is
0, the answer is0because that is the only digit present.If the number is negative, only its digits matter, so the minus sign should be ignored.
Dry Run
Find the Largest Digit in a Number Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Function to find the largest digit in a number. */ int findLargestDigit(long long n) { // Convert negative number to positive n = llabs(n); // Handle the case when the number is 0 if (n == 0) { return 0; } int largest = 0; // Process digits one by one while (n > 0) { int digit = n % 10; // Update the answer when a larger digit is found if (digit > largest) { largest = digit; } // Remove the last digit n /= 10; } return largest; }};int main() { // Driver code starts Solution solution; long long n = 58241; cout << solution.findLargestDigit(n) << "\n"; return 0;}Complexity Analysis
Time Complexity: O(log10 N), where log10 N is the number of digits in N and each digit is checked exactly once.
Space Complexity: O(1), because constant space is used.
Interview follow-up Questions
When a number is divided by 10, the remainder is always the last digit.
Be the first to add a comment.