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.
Note: A substring is a contiguous sequence of characters within a string. A null string (“”) is also a substring.
Examples:
Input: S = “504”
Output: “5”
Explanation: The only substring “5” is an odd number.Input: S = “2042”
Output: “”
Explanation: All the possible non-empty substrings have even values.
Approach: To solve the problem follow the below idea:
The idea is to check odd number from the last in the string just to return the largest odd number.
Follow the steps to solve the problem:
- Iterate through i = s.length – 1 till 0:
- Check if s[i] is odd then return the substring from 0 to i+1.
- Return an empty string in case of no odd number.
Below is the implementation for the above approach:
C++
// C++ code for the above approach: #include <iostream> using namespace std; string maxOdd(string s) { for ( int i = s.length() - 1; i >= 0; i--) { if (s[i] % 2 != 0) { string s1 = s.substr(0, i + 1); return s1; } } return "" ; } // Drivers code int main() { string s = "504" ; string ans = maxOdd(s); // Function Call cout << ans; return 0; } |
Java
// Java code for the above approach: import java.io.*; class GFG { // returns a substring that contains the maximum odd number at its end public static String maxOdd(String s) { // Loop through the string backwards, starting from the end for ( int i = s.length() - 1 ; i >= 0 ; i--) { // Check if the current character is odd if (s.charAt(i) % 2 != 0 ) { // If it is, return the substring that contains // all the characters up to and including the current character String s1 = s.substring( 0 , i + 1 ); return s1; } } // If no odd number is found in the string, return an empty string return "" ; } // driver functiom public static void main(String[] args) { String s = "504" ; // function call String ans = maxOdd(s); System.out.println(ans); } } |
Python
def max_odd(s): for i in range ( len (s) - 1 , - 1 , - 1 ): if int (s[i]) % 2 ! = 0 : return s[:i + 1 ] return "" # Driver code s = "504" ans = max_odd(s) # Function call print (ans) |
C#
// C# code for the above approach: using System; class GFG { // returns a substring that contains the maximum odd number at its end public static string maxOdd( string s) { // Loop through the string backwards, starting from the end for ( int i = s.Length - 1; i >= 0; i--) { // Check if the current character is odd if (s[i] % 2 != 0) { // If it is, return the substring that contains // all the characters up to and including the current character string s1 = s.Substring(0, i + 1); return s1; } } // If no odd number is found in the string, return an empty string return "" ; } // driver functiom public static void Main() { string s = "504" ; // function call string ans = maxOdd(s); Console.WriteLine(ans); } } // This code is contributed by Pushpesh Raj |
Javascript
// Javascript code for the above approach // returns a substring that contains the maximum odd number at its end function maxOdd(s) { // Loop through the string backwards, starting from the end for (let i = s.length - 1; i >= 0; i--) { // Check if the current character is odd if (parseInt(s.charAt(i)) % 2 !== 0) { // If it is, return the substring that contains // all the characters up to and including the current character return s.substring(0, i + 1); } } // If no odd number is found in the string, return an empty string return '' ; } // driver function const s = '504' ; // function call const ans = maxOdd(s); console.log(ans); // This code is contributed by Vaibhav Nandan. |
5
Time Complexity: O(|S|).
Auxiliary Space: O(1).
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!