Largest odd number in a string

Beginner Problems Basic Strings Easy

Fun Fact: A real-world application of such a problem can be found within Big Data Processing software and Financial Technologies (Fintech)
In these fields, there’s often a need to deal with large integers, convert them to strings and extract specific parts
For instance, certain aspects of financial analysis require the extraction of specific digits or series of digits from large numbers
Similarly in network security, similar tasks are required for cryptographic operations to encrypt or decrypt data
Thus problems like these underpin several major operations in Fintech and Security industry

Given a string s, representing a large integer, the task is to return the largest-valued odd integer (as a string) that is a substring of the given string s.

The number returned should not have leading zero's. But the given input string may have leading zero.

Examples:

Input : s = "5347"

Output : "5347"

Explanation : The odd numbers formed by given strings are --> 5, 3, 53, 347, 5347.

So the largest among all the possible odd numbers for given string is 5347.

Input : s = "0214638"

Output : "21463"

Explanation : The different odd numbers that can be formed by the given string are --> 1, 3, 21, 63, 463, 1463, 21463.

We cannot include 021463 as the number contains leading zero.

So largest odd number in given string is 21463.

Input : s = "0032579"

Constraints

1 <= s.length <= 10³
'0' <= s[i] <= '9'

Company Tags

TCS Cognizant Accenture Infosys Capgemini Wipro IBM HCL Tech Mahindra MindTree

Editorial

              document.body.innerHTML = '';
              const iframeHTML = `
                <div style="padding-top:56.25%;position:relative;">
                  <iframe 
                    src="https://app.tpstreams.com/embed/atsjxr/AmzSHjX8bdN/?access_token=33e345b1-9f22-4382-8c5c-7e49a75d8027" 
                    style="border:0;max-width:100%;position:absolute;top:0;left:0;height:100%;width:100%;" 
                    allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" 
                    allowfullscreen="" 
                    frameborder="0">
                  </iframe>
                </div>
              `;
              document.body.innerHTML = iframeHTML;
              
              const script = document.createElement('script');
              script.src = 'https://static.testpress.in/static/js/player.js';
              document.head.appendChild(script);
              
              script.onload = () => {
                const iframe = document.querySelector('iframe');
                const player = new Testpress.Player(iframe);
              
                player.loaded().then(() => {
                  console.log('Player is ready now');
                });
              
                player.on('play', () => {
                  console.log('Played the video');
                });
              };

Intuition

To determine the largest substring ending with an odd digit, start by iterating backward from the end of the number. This approach efficiently finds the rightmost odd digit by examining each character in reverse order. Once an odd digit is encountered, the substring from the beginning of the number up to and including this digit represents the largest possible odd-ending substring. This process leverages the fact that finding the last occurrence of an odd digit directly provides the longest valid substring.

Approach

1. Start by iterating through the string from the end towards the beginning to find the first odd digit. This digit marks the potential end of the largest odd number substring.

2. Once an odd digit is found, skip any leading zeroes from the beginning of the string up to this odd digit.

3. Extract and return the substring starting after the leading zeroes and ending at the identified odd digit. This substring represents the largest odd integer without leading zeroes.

Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    /* Function to find the largest odd number 
    that is a substring of given string */
    string largeOddNum(string& s) {
        int ind = -1;
        
        // Iterate through the string from the end to beginning
        int i;
        for (i = s.length() - 1; i >= 0; i--) {
            // Break if an odd digit is found
            if ((s[i] - '0') % 2 == 1) {
                ind = i;
                break;
            }
        }
        
        // Skipping any leading zeroes
        i = 0;
        while(i <= ind && s[i] == '0') i++;
        
        // Return the largest odd number substring
        return s.substr(i, ind - i + 1);
    }
};

int main() {
    Solution solution;
    string num = "504";
    string result = solution.largeOddNum(num);
    cout << "Largest odd number: " << result << endl;
    return 0;
}
import java.util.*;

class Solution {
    /* Function to find the largest odd number 
    that is a substring of given string */
    public String largeOddNum(String s) {
        int ind = -1;
        
        // Iterate through the string from the end to beginning
        int i;
        for (i = s.length() - 1; i >= 0; i--) {
            // Break if an odd digit is found
            if ((s.charAt(i) - '0') % 2 == 1) {
                ind = i;
                break;
            }
        }
        
        // If no odd number was found, return an empty string
        if (ind == -1) return "";
        
        // Skipping any leading zeroes
        i = 0;
        while(i <= ind && s.charAt(i) == '0') i++;
        
        // Return the largest odd number substring
        return s.substring(i, ind + 1);
    }
    
    public static void main(String[] args) {
        Solution solution = new Solution();
        String num = "504";
        String result = solution.largeOddNum(num);
        System.out.println("Largest odd number: " + result);
    }
}
class Solution:
    # Function to find the largest odd number 
    # that is a substring of given string 
    def largeOddNum(self, s: str) -> str:
        ind = -1
        
        # Iterate through the string from the end to beginning
        i = 0
        for i in range(len(s) - 1, -1, -1):
            # Break if an odd digit is found
            if (int(s[i]) % 2) == 1:
                ind = i
                break
        
        # Skipping any leading zeroes
        i = 0
        while i <= ind and s[i] == '0':
            i += 1
        
        # Return the largest odd number substring
        return s[i:ind + 1]

# Driver code
solution = Solution()
num = "504"
result = solution.largeOddNum(num)
print("Largest odd number:", result)
class Solution {
    /* Function to find the largest odd number 
    that is a substring of given string */
    largeOddNum(s) {
        let ind = -1;
        
        // Iterate through the string from the end to beginning
        let i;
        for (i = s.length - 1; i >= 0; i--) {
            // Break if an odd digit is found
            if ((s[i] - '0') % 2 === 1) {
                ind = i;
                break;
            }
        }
        
        // Skipping any leading zeroes
        i = 0;
        while (i <= ind && s[i] === '0') i++;
        
        // Return the largest odd number substring
        return s.substring(i, ind + 1);
    }
}

// Driver code
const solution = new Solution();
const num = "504";
const result = solution.largeOddNum(num);
console.log("Largest odd number:", result);

Complexity Analysis

Time Complexity O(N): The loop runs once through the string of length N.

Space Complexity O(1): No extra data structures are used only a few extra variables are used which does not affect the complexity as much.

Code

Problem List