1903. Largest Odd Number in String
Problem Description
In the given problem, we have to work with a string num that represents a large integer. The objective is to find a substring of this string that represents the largest odd integer. A substring is defined as a sequence of characters that are contiguous; in other words, the characters are next to each other without any gaps. If there are no odd integers at all in the string, then the function should return an empty string "". Simply put, we need to parse through the string to find the largest odd integer by examining various portions of the string, taking care not to break up the order of the characters as we do so. It's important to remember that an odd integer is one whose last digit is 1, 3, 5, 7, or 9.
Intuition
To solve this problem, we can use a straightforward approach. Since any leading zeros in a number do not affect its value, we can ignore them. What matters is the rightmost digit, because it determines if a number is odd or even. Therefore, we can scan the string from right to left, looking for the first odd digit (1, 3, 5, 7, or 9). Once we find it, we can take the substring that starts from the beginning of num and goes up to and includes this digit. This is the largest odd integer that can be formed as it includes the maximum number of leading digits from the original string.
If no odd digit is found by the time we reach the beginning of the string (index 0), then we return an empty string since it's not possible to form an odd integer from num. This method is efficient because we don't need to check every possible substring; we just stop at the rightmost odd digit. It works because any smaller substring ending with the same digit would be smaller or equal in value and thus would not be the maximum odd integer that could be formed.
What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?
Solution Approach
The solution makes use of a simple for-loop to iterate through the given string num. The loop runs in reverse, starting from the last character and moving towards the first. This is accomplished by setting the for-loop's range with len(num) - 1 as the starting index, -1 as the stop index, and -1 as the step, which means "move one step backward".
Here are the steps taken inside the for-loop in the solution:
-
Check if the current digit is an odd number:
- Convert the current character at index
ito an integer usingint(num[i]). - Determine if the last bit is set (which would make it odd) by using bitwise AND with
1.
- Convert the current character at index
-
If the condition
(int(num[i]) & 1) == 1meets:- It implies that the digit at index
iis odd. - We then use slicing to obtain the substring from the start of
numto the indexiinclusive, usingnum[: i + 1]. - This substring is then returned as it is the largest possible odd integer that can be formed from a substring of the original number.
- It implies that the digit at index
-
If no odd digit is found by the end of the loop:
- The for-loop exits without returning any value from inside the loop.
- The function then returns an empty string (
'') after the loop completes, signaling that no odd integer could be found withinnum.
No additional data structures are needed for this solution, keeping the space complexity at O(1), as we are returning a substring of the original input. The time complexity is O(N), where N is the length of the string, as we may potentially have to scan through the entire string once.
Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?
Example Walkthrough
Let's assume the string num is "1234567890". We need to find the largest odd integer that can be created as a substring from this number.
To do so, we follow the described solution approach and scan the string from right to left. That means we start with the last character of the string and move towards the first character:
- We start at index 9 (the last index of
num), which is the digit '0'. This is not an odd digit, so we move one step backward in the string. - At index 8, we find the digit '9', which is odd (converting to integer
int('9')and applying the bitwise AND operation with1results in1, thus it's odd). - Since we've encountered an odd digit, we take the substring from the start of
numto this index (inclusive). Using slicing, we extractnum[:8+1], which gives us "123456789". - "123456789" is the largest odd integer we can form from the substring of
num, so we return this value.
With this example, we can see that the method of scanning from right to left and taking the first odd number we come across gives us the largest possible odd integer in the form of a substring.
Solution Implementation
1class Solution:
2 def largest_odd_number(self, num: str) -> str:
3 # Start from the end of the string and move backwards
4 for i in range(len(num) - 1, -1, -1):
5 # Check if the current digit is odd
6 if int(num[i]) % 2 == 1:
7 # If an odd digit is found, return the substring up to this digit (inclusive)
8 return num[:i + 1]
9 # If no odd digit is found, return an empty string
10 return ''
11```
12
13I'll note that the method name `largest_odd_number` was changed from `largestOddNumber` to follow the Python convention of using snake_case for function and variable names. However, since the original method name `largestOddNumber` was likely provided by LeetCode and it may be required for the solution to be accepted by their system, you may want to retain the original camelCase method name.
14
15Here's the version maintaining the required LeetCode method name:
16
17```python
18class Solution:
19 def largestOddNumber(self, num: str) -> str:
20 # Iterate over the number string in reverse order
21 for i in range(len(num) - 1, -1, -1):
22 # Check if the current character represents an odd digit
23 if int(num[i]) % 2 == 1:
24 # If it does, return the substring from the start to the current character inclusive
25 return num[:i + 1]
26 # If no odd digit was found, return an empty string
27 return ''
281class Solution {
2 public String largestOddNumber(String num) {
3 // Iterate from the end of the string to the beginning
4 for (int index = num.length() - 1; index >= 0; index--) {
5 // Convert the character at the current index to an integer
6 int digit = num.charAt(index) - '0';
7
8 // Check if the digit is odd
9 if ((digit & 1) == 1) {
10 // If it's odd, return the substring from the start to the current index + 1
11 // This is because substring function in Java is end-exclusive
12 return num.substring(0, index + 1);
13 }
14 }
15
16 // If no odd digit is found, return an empty string
17 return "";
18 }
19}
201#include <string>
2
3class Solution {
4public:
5 // Function to find the largest odd number string from the input string 'num'
6 string largestOddNumber(string num) {
7 // Iterate from the end of the string towards the beginning
8 for (int index = num.size() - 1; index >= 0; --index) {
9 // Convert the current character to its numerical value
10 int digit = num[index] - '0';
11
12 // Check if the digit is odd using bitwise AND operation
13 if ((digit & 1) == 1) {
14 // If odd, return the substring from the beginning up to the current index (inclusive)
15 return num.substr(0, index + 1);
16 }
17 }
18 // If no odd number is found, return an empty string
19 return "";
20 }
21};
221/**
2 * Given a numeric string, this function finds and returns the largest odd number
3 * that can be formed by a substring of the input.
4 * If no odd number can be formed, it returns an empty string.
5 *
6 * @param {string} num - The numeric string from which to extract the largest odd number.
7 * @return {string} - The largest odd number that can be formed, or an empty string if not possible.
8 */
9function largestOddNumber(num: string): string {
10 // Get the length of the numeric string.
11 const numLength: number = num.length;
12
13 // Iterate over the string from end to start.
14 for (let index = numLength - 1; index >= 0; index--) {
15 // Check if the current character represents an odd digit.
16 if (parseInt(num.charAt(index)) % 2 === 1) {
17 // Return the substring from start to the current odd digit (inclusive).
18 return num.slice(0, index + 1);
19 }
20 }
21
22 // If no odd number found, return an empty string.
23 return '';
24};
25Depth first search can be used to find whether two components in a graph are connected.
Time and Space Complexity
Time Complexity
The time complexity of the provided code is O(n), where n is the length of the input string num. This is because the code consists of a single loop that iterates over the string from the end towards the beginning. In the worst-case scenario, the loop runs for the entire length of the string if the last odd number is at the beginning of the string or there is no odd number at all.
Space Complexity
The space complexity of the code is O(1). No additional space is used that grows with the size of the input. The return statement num[: i + 1] creates a new string, but since string slicing in Python does not create a new copy of the characters (instead, it just creates a new view of the original string), the space used does not depend on the size of the input string.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of these pictures shows the visit order of a depth-first search?
Recommended Readings
Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.