Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. An integer is odd exactly when its last digit is odd.
  2. 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