Largest Odd Number in String

🏠 ⬅️ ➡️

You are given a string num, representing a large integer. Return the largest-valued odd integer (as a string) that is a non-empty substring of num, or an empty string " " if no odd integer exists.

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: num = "52 " Output: "5 " Explanation: The only non-empty substrings are "5 ", "2 ", and "52 ". "5 " is the only odd number.

Example 2:

Input: num = "4206 " Output: " " Explanation: There are no odd numbers in "4206 ".

Example 3:

Input: num = "35427 " Output: "35427 " Explanation: "35427 " is already an odd number.

Constraints:

  • 1 <= num.length <= 105
  • num only consists of digits and does not contain any leading zeros.
Note: This problem is from LeetCode.
✅ Compiled
✅ Executed
❌ Correct 
program main
    implicit none

    character(len=100) :: num, largest_odd

    ! Example 1
    num = "52 "
    call get_largest_odd(num, largest_odd)
    print '("Example 1: ", A)', largest_odd

    ! Example 2
    num = "4206 "
    call get_largest_odd(num, largest_odd)
    print '("Example 2: ", A)', largest_odd

    ! Example 3
    num = "35427 "
    call get_largest_odd(num, largest_odd)
    print '("Example 3: ", A)', largest_odd

contains

    subroutine get_largest_odd(num, largest_odd)
        implicit none
        character(len=*), intent(in) :: num
        character(len=*), intent(out) :: largest_odd
        integer :: i, j, k

        largest_odd = ""
        do i = len(num), 1, -1
            if (num(i:i) == " ") cycle
            if (num(i:i) /= "0") then
                do j = i + 1, len(num)
                    if (num(j:j) == " ") exit
                    if (num(j:j) /= "0") then
                        largest_odd = num(i:j)
                        return
                    end if
                end do
            end if
        end do
    end subroutine get_largest_odd

end program main
❌ Compiled
❌ Executed
❌ Correct 
program largestOddNumber
      implicit none

      integer :: i, j, k, n
      character(len=100) :: num, largest_odd

      ! Read the input string
      read(*,*) num

      ! Initialize the largest odd number to an empty string
      largest_odd = " "

      ! Iterate over the characters in the input string
      do i = 1, len_trim(num)

         ! Check if the current character is a digit
         if (num(i:i) >= '0' .and. num(i:i) <= '9') then

            ! Convert the current character to an integer
            read(num(i:i),*) n

            ! Check if the current number is odd
            if (mod(n,2) == 1) then

               ! Check if the current number is the largest odd number so far
               if (largest_odd == " ") then
                  largest_odd = num(i:i)
               else
                  ! Compare the current number with the largest odd number so far
                  if (n > largest_odd) then
                     largest_odd = num(i:i)
                  end if
               end if
            end if
         end if
      end do

      ! Print the largest odd number
      print*, largest_odd

      end program
🌐 Data from online sources 
def largest_odd_number(num: str) -> str:
    for i in range(len(num) - 1, -1, -1):
        if int(num[i]) % 2 != 0:
            return num[:i + 1]
    return ""

The algorithm starts iterating through the given string num from the last character to the first one. Since we only need the largest odd number as a substring, we only need to find the first odd digit when iterating from right to left. When we find an odd digit, that means the current non-empty substring is the largest odd number, and we return that substring. If no odd digits are found, the function returns an empty string. The time complexity is O(n), where n is the length of the string num.

🌐 Data from online sources 
std::string largestOddNumber(std::string num) {
    for (int i = num.length() - 1; i >= 0; i--) {
        if ((num[i] - '0') % 2 != 0) {
            return num.substr(0, i + 1);
        }
    }
    return "";
}

The algorithm starts iterating through the given string num from the last character to the first one. Since we only need the largest odd number as a substring, we only need to find the first odd digit when iterating from right to left. When we find an odd digit, that means the current non-empty substring is the largest odd number, and we return that substring. If no odd digits are found, the function returns an empty string. The time complexity is O(n), where n is the length of the string num.