The task is to find the largest-valued odd number that can be formed from a given numeric string by removing trailing even digits. The number must be a substring starting from index 0 to some valid index.
Steps
- Start from the end of the string and move backward.
- Check if the current digit is odd using modulus
% 2. - If an odd digit is found, return the substring from index 0 to that digit (inclusive).
- If no odd digit exists in the string, return an empty string.
Dry Run
Input: "52"
- Start from the end: ‘2’ → even → skip
- Next: ‘5’ → odd → return
"5"
Time & Space Complexity
- Time Complexity: O(n), where n is the length of the string
- Space Complexity: O(1), no extra space used
var largestOddNumber = function(s) {
let n = s.length - 1;
while (n >= 0) {
if (Number(s[n]) % 2 == 1) {
return s.substring(0, n + 1);
}
--n;
}
return "";
};
#include <iostream>
using namespace std;
string largestOddNumber(string s) {
int n = s.length() - 1;
while (n >= 0) {
if ((s[n] - '0') % 2 == 1) {
return s.substr(0, n + 1);
}
--n;
}
return "";
}
#include <stdio.h>
#include <string.h>
void largestOddNumber(char* s, char* result) {
int n = strlen(s) - 1;
while (n >= 0) {
if ((s[n] - '0') % 2 == 1) {
strncpy(result, s, n + 1);
result[n + 1] = '\0';
return;
}
--n;
}
result[0] = '\0';
}
public class Solution {
public String largestOddNumber(String s) {
int n = s.length() - 1;
while (n >= 0) {
if ((s.charAt(n) - '0') % 2 == 1) {
return s.substring(0, n + 1);
}
n--;
}
return "";
}
}
def largestOddNumber(s: str) -> str:
n = len(s) - 1
while n >= 0:
if int(s[n]) % 2 == 1:
return s[:n+1]
n -= 1
return ""
