Given an integer N, the task is to find the Nth number made up of odd digits (1, 3, 5, 7, 9) only.
The first few numbers made up of odd digits are 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 31, …
Examples:
Input: N = 7
Output: 13
1, 3, 5, 7, 9, 11, 13
13 is the 7th number in the seriesInput: N = 10
Output: 19
Approach 1 (Simple) : Starting from 1, keep checking if the number is made up of only odd digits (1, 3, 5, 7, 9) and stop when nth such number is found.
Below is the implementation of the above approach:
C++
// C++ program to find nth number made up of odd digits only#include <bits/stdc++.h>using namespace std;// Function to return nth number made up of odd digits onlyint findNthOddDigitNumber(int n){ // Variable to keep track of how many // such elements have been found int count = 0; for (int i = 1;; i++) { int num = i; bool isMadeOfOdd = true; // Checking each digit of the number while (num != 0) { // If 0, 2, 4, 6 or 8 is found // then the number is not made up of odd digits if (num % 10 == 0 || num % 10 == 2 || num % 10 == 4 || num % 10 == 6 || num % 10 == 8) { isMadeOfOdd = false; break; } num = num / 10; } // If the number is made up of odd digits only if (isMadeOfOdd == true) count++; // If it is the nth number if (count == n) return i; }}// Driver Codeint main(){ int n = 10; cout << findNthOddDigitNumber(n); return 0;} |
Java
// Java program to find nth number // made up of odd digits only import java.io.*;class GFG { // Function to return nth number made up of odd digits only static int findNthOddDigitNumber(int n) { // Variable to keep track of how many // such elements have been found int count = 0; for (int i = 1;; i++) { int num = i; boolean isMadeOfOdd = true; // Checking each digit of the number while (num != 0) { // If 0, 2, 4, 6 or 8 is found // then the number is not made up of odd digits if (num % 10 == 0 || num % 10 == 2 || num % 10 == 4 || num % 10 == 6 || num % 10 == 8) { isMadeOfOdd = false; break; } num = num / 10; } // If the number is made up of odd digits only if (isMadeOfOdd == true) count++; // If it is the nth number if (count == n) return i; } } // Driver Code public static void main (String[] args) { int n = 10; System.out.println (findNthOddDigitNumber(n)); }//This code is contributed by ajit } |
Python3
# Python3 program to find nth number # made up of odd digits only# Function to return nth number made# up of odd digits onlydef findNthOddDigitNumber(n) : # Variable to keep track of how many # such elements have been found count = 0 i = 1 while True : num = i isMadeOfOdd = True # Checking each digit of the number while num != 0 : # If 0, 2, 4, 6 or 8 is found # then the number is not made # up of odd digits if (num % 10 == 0 or num % 10 == 2 or num % 10 == 4 or num % 10 == 6 or num % 10 == 8) : isMadeOfOdd = False break num //= 10 # If the number is made up of # odd digits only if isMadeOfOdd == True : count += 1 # If it is the nth number if count == n : return i i += 1# Driver codeif __name__ == "__main__" : n = 10 # Function call print(findNthOddDigitNumber(n)) # This code is contributed by Ryuga |
C#
// C# program to find nth number // made up of odd digits only using System;class GFG{ // Function to return nth number // made up of odd digits only static int findNthOddDigitNumber(int n) { // Variable to keep track of // how many such elements have // been found int count = 0; for (int i = 1;; i++) { int num = i; bool isMadeOfOdd = true; // Checking each digit // of the number while (num != 0) { // If 0, 2, 4, 6 or 8 is found // then the number is not made // up of odd digits if (num % 10 == 0 || num % 10 == 2 || num % 10 == 4 || num % 10 == 6 || num % 10 == 8) { isMadeOfOdd = false; break; } num = num / 10; } // If the number is made up of // odd digits only if (isMadeOfOdd == true) count++; // If it is the nth number if (count == n) return i; } } // Driver Code static public void Main (){ int n = 10; Console.WriteLine(findNthOddDigitNumber(n)); }}// This code is contributed // by Ajit Deshpal |
PHP
<?php// PHP program to find nth number // made up of odd digits only// Function to return nth number// made up of odd digits onlyfunction findNthOddDigitNumber($n){ // Variable to keep track of how many // such elements have been found $count = 0; $i = 1; while (true) { $num = $i; $isMadeOfOdd = true; // Checking each digit of // the number while ($num != 0) { // If 0, 2, 4, 6 or 8 is found // then the number is not made // up of odd digits if ($num % 10 == 0 or $num % 10 == 2 or $num % 10 == 4 or $num % 10 == 6 or $num % 10 == 8) { $isMadeOfOdd = false; break; } $num = (int)($num / 10); } // If the number is made up of // odd digits only if ($isMadeOfOdd == true) $count += 1; // If it is the nth number if ($count == $n) return $i; $i += 1; }}// Driver code$n = 10;// Function callprint(findNthOddDigitNumber($n)); // This code is contributed by mits?> |
Javascript
<script>// JavaScript program to find nth // number made up of odd digits only// Function to return nth number // made up of odd digits onlyfunction findNthOddDigitNumber(n){ // Variable to keep track of how many // such elements have been found let count = 0; for(let i = 1;; i++) { let num = i; let isMadeOfOdd = true; // Checking each digit of the number while (num != 0) { // If 0, 2, 4, 6 or 8 is found // then the number is not made // up of odd digits if (num % 10 == 0 || num % 10 == 2 || num % 10 == 4 || num % 10 == 6 || num % 10 == 8) { isMadeOfOdd = false; break; } num = Math.floor(num / 10); } // If the number is made up of // odd digits only if (isMadeOfOdd == true) count++; // If it is the nth number if (count === n) return i; }}// Driver Codelet n = 10;document.write(findNthOddDigitNumber(n));// This code is contributed by Manoj.</script> |
Output
19
Time Complexity: O(n log10n), where N represents the size integer.
Auxiliary Space: O(1), no extra space is required, so it is a constant.
Approach 2 (Queue Based):
The idea is to generate all numbers (smaller than n) containing odd digits only. How to generate all numbers smaller than n with odd digits? We use queue for this. Initially, we push ‘1’, ‘3’, ‘5’, ‘7’ and ‘9’ to the queue. Then we run a loop while count of processed elements is smaller than n.
We pop an item one by one and for every popped item x, we generate next numbers x*10 + 1, x*10 + 3, x*10 + 5, x*10 + 7 and x*10 + 9. We enqueue these new numbers.
Time complexity of this approach is O(n)
Count of Binary Digit numbers smaller than N
Approach 3 (Bit Manipulation)
If we observe the pattern then it is similar to the pattern of consecutive bits in base 5 then it is similar to the pattern which we find in this problem.
Base 5: 0 1 2 3 4
Required: 1 3 5 7 9
So we can store 1, 3, 5, 7, 9 in an array and find the bit required in base 5 representation and substitute the required number in place of that.
But we need to take care of one more thing that whenever N is divisible by 5 then last place should be 9 and after dividing the number by 5 we need to decrement it by 1 in this case. Hence array should be in the form {9, 1, 3, 5, 7}
- Create an array v[] for the values to be replaced.
- Initialize a variable ans = 0.
- Do the following until N is greater than 0
- Find the remainder of N with 5. If the remainder is 0
- If true, add v[0] to the answer and divide N by 5 and reduce it by 1.
- Otherwise, simply add v[remainder] in the ans and divide N by 5.
- Find the remainder of N with 5. If the remainder is 0
- Now all that is left is to reverse the number and we get the required number.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;long long findNumber(long long N){ vector<int> v = { 9, 1, 3, 5, 7 }; long long ans = 0; while (N > 0) { ans = ans * 10 + v[N % 5]; if (N % 5 == 0) { N = N / 5; N--; } else N /= 5; } queue<int> q; while (ans > 0) { q.push(ans % 10); ans /= 10; } while (!q.empty()) { ans = ans * 10 + q.front(); q.pop(); } return ans;}int main(){ int N = 7; cout << findNumber(N) << endl; return 0;} |
Java
// Java code to implement the approachimport java.util.*;public class gfg2 { static long findNumber(int N) { int[] v = { 9, 1, 3, 5, 7 }; int ans = 0; while (N > 0) { ans = ans * 10 + v[N % 5]; if (N % 5 == 0) { N = N / 5; N--; } else N /= 5; } Queue<Integer> q = new ArrayDeque<>(); while (ans > 0) { q.add(ans % 10); ans /= 10; } while (!q.isEmpty()) { ans = ans * 10 + q.peek(); q.remove(); } return ans; } public static void main(String[] args) { int N = 7; System.out.println(findNumber(N)); }}// This code is contributed by karandeep1234 |
Python3
# Python code to implement the approachdef findNumber(N): v = [9, 1, 3, 5, 7] ans = 0 while(N > 0): ans = ans * 10 + v[N % 5] if(N % 5 == 0): N = N//5 N = N - 1 else: N = N//5 q = [] while(ans > 0): q.append(ans % 10) ans = ans//10 while(len(q) > 0): ans = ans * 10 + q[0] q.pop(0) return ansN = 7print(findNumber(N))# This code is contributed by Pushpesh Raj. |
C#
// C# code for above approachusing System;using System.Collections.Generic;public class GFG { public static long findNumber(int N) { int[] v = new int[5] { 9, 1, 3, 5, 7 }; int ans = 0; while (N > 0) { ans = ans * 10 + v[N % 5]; if (N % 5 == 0) { N = N / 5; N--; } else N /= 5; } List<int> q = new List<int>(); while (ans > 0) { q.Add(ans % 10); ans /= 10; } while (q.Count != 0) { ans = ans * 10 + q[0]; q.RemoveAt(0); } return ans; } public static void Main(string[] args) { int N = 7; Console.WriteLine(findNumber(N)); }}// This code is contributed by ishankhandelwals. |
Javascript
function findNumber(N) { let v = [9, 1, 3, 5, 7] let ans = 0 while (N > 0) { ans = (ans * 10) + v[N % 5] if (N % 5 == 0) { N = Math.floor(N / 5); N--; } else N = Math.floor(N / 5); } let q = []; while (ans > 0) { q.push(ans % 10); ans = Math.floor(ans / 10); } while (q.length != 0) { ans = ans * 10 + q[0]; q.shift(); } return ans;}N = 7console.log(findNumber(N))// This code is contributed by ishankhandelwals. |
Output
13
Time Complexity: O(log5N)
Auxiliary Space: O(log5N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
