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 codeint 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 codes = "504"ans = max_odd(s)# Function callprint(ans) |
C#
// C# code for the above approach:using System;class GFG {// returns a substring that contains the maximum odd number at its endpublic 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 functiompublic 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 endfunction 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 oddif (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. |
Output
5
Time Complexity: O(|S|).
Auxiliary Space: O(1).
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
