Problem

Problem_Link

Problem Solving Approach

• Odd digit numbers have a pattern

  | 1 | 3 | 5 | 7 | 9 | | --- | --- | --- | --- | --- | | 11 | 13 | 15 | 17 | 19 | | 31 | 33 | 35 | 37 | 39 | | 51 | 53 | 55 | 57 | 59 | | 71 | 73 | 75 | 77 | 79 | | 91 | 93 | 95 | 97 | 99 | | 101 | 103 | 105 | 107 | 109 |

• As seen above, the pattern repeats every 5 numbers.

• Therefore, we can know the position of each digit by dividing N by 5.

• If we know the position of each digit, we can find out what number will be in that position (1, 3, 5, 7, 9)

• Let's take the 13th odd digit number as an example

  • The rightmost digit (ones place) in 13 is the 3rd.

  • According to the odd digit pattern, the third number is 5.

  • The second rightmost digit (tens place) in 13 is the 2nd.

  • According to the odd digit pattern, the second number is 3.

  • In conclusion, the 13th odd digit number is 35.

• Let's take the 27th odd digit number as an example

  • The rightmost digit (ones place) in 27 is the (27%5) 2nd.

  • According to the odd digit pattern, the second number is 3.

  • Excluding the calculated digits from 27, we get 27-27%5 = 27/5=5.

  • The second rightmost digit (tens place) is the (5%5) 5th.

  • According to the odd digit pattern, the fifth number is 9.

  • In conclusion, the 27th odd digit number is 93.

• There is something slightly incorrect with the above pattern. For example, 5%5 is 0. However, we want the pattern to follow the table above.

    - n % 5 = 0 //5th number = 9
    - n % 5 = 1 //1th number = 1
    - n % 5 = 2 //2th number = 3
    - n % 5 = 3 //3th number = 5
    - n % 5 = 4 //4th number = 7
  

  To fix this, we subtract 1 from n.

    - n-1 % 5 = 0 //1th number = 1
    - n-1 % 5 = 1 //2th number = 3
    - n-1 % 5 = 2 //3th number = 5
    - n-1 % 5 = 3 //4th number = 7
    - n-1 % 5 = 4 //5th number = 9
  

• Lastly, when we get 0, 1, 2, 3, 4, the actual numbers we want are 1, 3, 5, 7, 9. To optimize this, we multiply by 2 and add 1.

    0*2+1=1
    2*2+1=3
    3*2+1=5
    4*2+1=7
    5*2+1=9
  

Time O(log n), Space O(1)

https://github.com/eunhanlee/findNumber_Solution_gfg.git

class Solution
{
    /**
     * Finds the Nth number containing only odd digits.
     *
     * @param N The position of the desired number.
     * @return The Nth number containing only odd digits.
     */
    public long findNumber(long N)
    {
        // The variable to store the final result
        long result = 0;
        // The variable to represent the digit position (1, 10, 100, ...)
        long position = 1;

        // Continue until N is greater than 0
        while (N > 0)
        {
            // Calculate the odd digit by subtracting 1 from N and dividing by 5
            long oddDigit = ((N - 1) % 5) * 2 + 1;
            // Subtract 1 from N and divide by 5 to prepare for the next digit calculation
            N = (N - 1) / 5;
            // Add the odd digit multiplied by the current position to the result
            result += oddDigit * position;
            // Move to the next digit position
            position *= 10;
        }

        // Return the Nth number containing only odd digits
        return result;
    }
}

Explanation

• The given integer N is repeatedly divided by 5 during the computation process, which reduces its value. In this process, odd-digit numbers are generated. The loop continues as long as N is greater than 0.

• With each iteration, N is updated to (N - 1) / 5. This process reduces N by more than half, causing N to decrease significantly with each iteration. Since N is almost halved with each iteration, the time complexity can be considered as O(log N).