Largest Odd Number in String

Good day! Hope your day has started on the right note. The weather has been behaving somewhat strange this season. We started with very hot days and little precipitation. Such conditions caused many patches of dry grass to appear on lawns all over the Twin Cities of Minneapolis and St. Paul. In the past few days it has been raining on and off. That has helped lawns. I checked the weather forecast for today and my wife and I were planning on having breakfast and then head out for a walk. The forecast was off. We had precipitation for the first few hours, so after breakfast I showered, got dressed and went down to my home office.

In a previous post I mentioned that I was going to participate in a weekly programming contest. The contest was scheduled for last Saturday. When I woke up we had rain and thunderstorms. In the past decade or so I have lost two KVM switches. After replacing the second switch I decided to shutdown all my computers when there is a thunderstorm in the area. I canceled my participation in the contest. Will check if there is one this weekend. Will let you know my findings.

I decided to take a look at LeetCode 1903 Largest Odd Number in String problem.

You are given a string num, representing a large integer. 
Return the largest-valued odd integer (as a string) that is a non-empty substring of num, 
or an empty string "" if no odd integer exists.

A substring is a contiguous sequence of characters within a string.

We are given a string of numbers and we need to return the largest-values odd integer.

The approach is to take the string and remove even digits from the right. The process should stop when the string s empty or when we encounter and odd number.

    public String largestOddNumber(String num) {
        
    }

I will solve the problem using the Java programming language and the VSCode IDE on a Windows computer. The signature for the function in question is quite simple. It takes a string on integers and returns a string with the largest odd number.

I could have used the on-line IDE provided by LeetCode, but decided to write my own test scaffold and solve the problem on my computer. Unless you have a good reason, go ahead and use the on-line IDE provided by LeetCode.


main <<< num ==><==
main <<< largestOddNumber ==><==


0
main <<< num ==>0<==
main <<< largestOddNumber ==><==


3
main <<< num ==>3<==
main <<< largestOddNumber ==>3<==


52
main <<< num ==>52<==
main <<< largestOddNumber ==>5<==


4206
main <<< num ==>4206<==
main <<< largestOddNumber ==><==


35427
main <<< num ==>35427<==
main <<< largestOddNumber ==>35427<==

There is only one input line. Our test code needs to read the line with integers, assign it to a String variable and for sanity check purpose display it to make sure all is well so far.

We then need to call the function of interest with the specified String argument, generate the result and display it.

    /**
     * Test scaffold.
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {
        
        // **** open buffered reader ****
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // **** read num string ****
        String num = br.readLine().trim();

        // **** close buffered reader ****
        br.close();

        // ???? ????
        System.out.println("main <<< num ==>" + num + "<==");

        // **** call function of interest and display result ****
        System.out.println("main <<< largestOddNumber ==>" + largestOddNumber(num) + "<==");
    }

Our test code seems to match quite closely the description associated with the test cases. I have nothing else to add to it at this time.

    /**
     * You are given a string num, representing a large integer. 
     * Return the largest-valued odd integer (as a string) that is 
     * a non-empty substring of num, 
     * or an empty string "" if no odd integer exists.
     * 
     * A substring is a contiguous sequence of characters within a string.
     * 
     * Time: O(n)  Space: O(n)
     * 
     * Runtime: 1 ms, faster than 99.97% of Java online submissions.
     * Memory Usage: 39.6 MB, less than 92.88% of Java online submissions.
     */
    static String largestOddNumber(String num) {
        
        // **** sanity check(s) ****
        if (num.length() == 0 || num.equals("0")) return "";

        // **** look for odd digit (right to left) ****
        for (int i = num.length() - 1; i >= 0; i--) {

            // **** check if odd ****
            if (num.charAt(i) % 2 == 1)
                return num.substring(0, i + 1);
        }

        // **** odd substring not found ****
        return "";
    }

We start the function of interest by performing a sanity check.

We then set a loop to traverse the input string from right to left.

We check if the current integer is odd. If so we return a substring with the result.

If we do not find an odd number or traverse the entire string, this is an indication that we do not have an odd number so as required, we return an empty string.

Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.

If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.

Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.

Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.

Regards;

John

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.