Practice › Strings
Largest Odd Number in a String
Easy · Strings · Asked at Amazon, TCS, Infosys, Wipro
The string num is a large integer without leading zeros. Print the largest-valued odd integer that is a non-empty substring of num. If there is none, print -1.
Input
A single string of digits num.
Output
The largest odd substring, or -1.
Constraints
- 1 ≤ |num| ≤ 10^5
A number is odd if its last digit is odd. The longest prefix ending at the rightmost odd digit is the answer.
Example 1
Input
52
Output
5
Example 2
Input
4206
Output
-1
Hints
- An integer is odd exactly when its last digit is odd.
- Longer numbers (without leading zeros) are larger, so keep as much of the front as possible.
Approach
The best substring starts at index 0 (the input has no leading zeros, and a longer number is larger) and must end on an odd digit. So find the rightmost odd digit and print the prefix up to it. If no digit is odd, print -1. Never convert to a number — the string can have 10^5 digits.
Complexity: O(n) time · O(1) extra space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
cin >> s;
for (int i = (int)s.size() - 1; i >= 0; i--) {
if ((s[i] - '0') % 2 == 1) {
cout << s.substr(0, i + 1) << "\n";
return 0;
}
}
cout << -1 << "\n";
return 0;
}Python solution
s = input().strip()
i = len(s) - 1
while i >= 0 and int(s[i]) % 2 == 0:
i -= 1
print(s[: i + 1] if i >= 0 else -1)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
String s = new Scanner(System.in).next();
for (int i = s.length() - 1; i >= 0; i--) {
if ((s.charAt(i) - '0') % 2 == 1) {
System.out.println(s.substring(0, i + 1));
return;
}
}
System.out.println(-1);
}
}Solve Largest Odd Number in a String online · All practice problems