Smallest odd digits number not less than N
Last Updated :
11 Apr, 2023
Given a number N, the task is to find the smallest number not less than N, which has all digits odd.
Examples:
Input: N = 1345
Output: 1351
1351 is the smallest number not less than N, whose all digits are odd.
Input: N = 2397
Output: 3111
3111 is the smallest number not less than N, whose all digits are odd.
Naive approach: A naive approach is to keep iterating from N until we find a number with all digits odd.
Below is the implementation of the above approach:
C++
// CPP program to print the smallest
// integer not less than N with all odd digits
#include <bits/stdc++.h>
using namespace std;
// function to check if all digits
// are odd of a given number
int check_digits(int n)
{
// iterate for all digits
while (n) {
if ((n % 10) % 2 == 0) // if digit is even
return 0;
n /= 10;
}
// all digits are odd
return 1;
}
// function to return the smallest number
// with all digits odd
int smallest_number(int n)
{
// iterate till we find a
// number with all digits odd
for (int i = n;; i++)
if (check_digits(i))
return i;
}
// Driver Code
int main()
{
int N = 2397;
cout << smallest_number(N);
return 0;
}
// Java program to print the smallest
// integer not less than N with all odd digits
import java.io.*;
class Geeks {
// function to check if all digits
// are odd of a given number
static int check_digits(int n)
{
// iterate for all digits
while (n > 0) {
if ((n % 10) % 2 == 0) // if digit is even
return 0;
n /= 10;
}
// all digits are odd
return 1;
}
// function to return the smallest number
// with all digits odd
static int smallest_number(int n)
{
// iterate till we find a
// number with all digits odd
for (int i = n;; i++)
if (check_digits(i) > 0)
return i;
}
// Driver Code
public static void main(String args[])
{
int N = 2397;
System.out.println(smallest_number(N));
}
}
// This code is contributed by Kirti_Mangal
# Python 3 program to print the smallest
# integer not less than N with all odd digits
# function to check if all digits
# are odd of a given number
def check_digits(n):
# iterate for all digits
while (n):
# if digit is even
if ((n % 10) % 2 == 0):
return 0
n = int(n / 10)
# all digits are odd
return 1
# function to return the smallest
# number with all digits odd
def smallest_number(n):
# iterate till we find a
# number with all digits odd
i = n
while(1):
if (check_digits(i)):
return i
i += 1
# Driver Code
if __name__ == '__main__':
N = 2397
print(smallest_number(N))
# This code is contributed by
# Sanjit_Prasad
// C# program to print the smallest
// integer not less than N with all
// odd digits
using System;
class GFG
{
// function to check if all digits
// are odd of a given number
static int check_digits(int n)
{
// iterate for all digits
while (n != 0)
{
if ((n % 10) % 2 == 0) // if digit is even
return 0;
n /= 10;
}
// all digits are odd
return 1;
}
// function to return the smallest
// number with all digits odd
static int smallest_number(int n)
{
// iterate till we find a
// number with all digits odd
for (int i = n;; i++)
if (check_digits(i) == 1)
return i;
}
// Driver Code
static void Main()
{
int N = 2397;
Console.WriteLine(smallest_number(N));
}
}
// This code is contributed by ANKITRAI1
<?php
// PHP program to print the smallest
// integer not less than N with all
// odd digits
// function to check if all digits
// are odd of a given number
function check_digits($n)
{
// iterate for all digits
while ($n > 1)
{
// if digit is even
if (($n % 10) % 2 == 0)
return 0;
$n = (int)$n / 10;
}
// all digits are odd
return 1;
}
// function to return the smallest
// number with all digits odd
function smallest_number( $n)
{
// iterate till we find a
// number with all digits odd
for ($i = $n;; $i++)
if (check_digits($i))
return $i;
}
// Driver Code
$N = 2397;
echo smallest_number($N);
// This code is contributed by ajit
?>
<script>
// java script program to print the smallest
// integer not less than N with all
// odd digits
// function to check if all digits
// are odd of a given number
function check_digits(n)
{
// iterate for all digits
while (n > 1)
{
// if digit is even
if ((n % 10) % 2 == 0)
return 0;
n = parseInt(n / 10);
}
// all digits are odd
return 1;
}
// function to return the smallest
// number with all digits odd
function smallest_number( n)
{
// iterate till we find a
// number with all digits odd
for (i = n;; i++)
if (check_digits(i))
return i;
}
// Driver Code
let N = 2397;
document.write( smallest_number(N));
// This code is contributed by sravan kumar (vignan)
</script>
Complexity Analysis:
- Time Complexity: O(N)
- Auxiliary Space: O(1)
Efficient Approach:
We can find the number by increasing the first even digit in N by one and replacing all digits to the right of that odd digit with the smallest odd digit (i.e. 1). If there are no even digits in N, then N is the smallest number itself. For example, consider N = 213. Increment first even digit in N i.e., 2 to 3 and replace all digits right to it by 1. So, our required number will be 311.
Below is the implementation of the efficient approach:
C++
// CPP program to print the smallest
// integer not less than N with all odd digits
#include <bits/stdc++.h>
using namespace std;
// function to return the smallest number
// with all digits odd
int smallestNumber(int n)
{
int num = 0;
string s = "";
int duplicate = n;
// convert the number to string to
// perform operations
while (n) {
s.push_back(((n % 10) + '0'));
n /= 10;
}
reverse(s.begin(), s.end());
int index = -1;
// find out the first even number
for (int i = 0; i < s.length(); i++) {
int digit = s[i] - '0';
if ((digit & 1) == 0) {
index = i;
break;
}
}
// if no even numbers are there, than n is the answer
if (index == -1)
return duplicate;
// add all digits till first even
for (int i = 0; i < index; i++)
num = num * 10 + (s[i] - '0');
// increase the even digit by 1
num = num * 10 + (s[index] - '0' + 1);
// add 1 to the right of the even number
for (int i = index + 1; i < s.length(); i++)
num = num * 10 + 1;
return num;
}
// Driver Code
int main()
{
int N = 2397;
cout << smallestNumber(N);
return 0;
}
//Java program to print the smallest
// integer not less than N with all odd digits
import java.io.*;
public class GFG {
// function to return the smallest number
// with all digits odd
static int smallestNumber(int n) {
int num = 0;
String s = "";
int duplicate = n;
// convert the number to string to
// perform operations
while (n > 0) {
s = (char) (n % 10 + 48) + s;
n /= 10;
}
int index = -1;
// find out the first even number
for (int i = 0; i < s.length(); i++) {
int digit = s.charAt(i) - '0';
if ((digit & 1) == 0) {
index = i;
break;
}
}
// if no even numbers are there, than n is the answer
if (index == -1) {
return duplicate;
}
// add all digits till first even
for (int i = 0; i < index; i++) {
num = num * 10 + (s.charAt(i) - '0');
}
// increase the even digit by 1
num = num * 10 + (s.charAt(index) - '0' + 1);
// add 1 to the right of the even number
for (int i = index + 1; i < s.length(); i++) {
num = num * 10 + 1;
}
return num;
}
// Driver Code
static public void main(String[] args) {
int N = 2397;
System.out.println(smallestNumber(N));
}
}
/*This code is contributed by PrinciRaj1992*/
# Python 3 program to print the smallest
# integer not less than N with all odd digits
# function to return the smallest
# number with all digits odd
def smallestNumber(n):
num = 0
s = ""
duplicate = n
# convert the number to string to
# perform operations
while (n):
s = chr(n % 10 + 48) + s
n //= 10
index = -1
# find out the first even number
for i in range(len( s)):
digit = ord(s[i]) - ord('0')
if ((digit & 1) == 0) :
index = i
break
# if no even numbers are there,
# than n is the answer
if (index == -1):
return duplicate
# add all digits till first even
for i in range( index):
num = num * 10 + (ord(s[i]) -
ord('0'))
# increase the even digit by 1
num = num * 10 + (ord(s[index]) -
ord('0') + 1)
# add 1 to the right of the
# even number
for i in range(index + 1 , len(s)):
num = num * 10 + 1
return num
# Driver Code
if __name__ == "__main__":
N = 2397
print(smallestNumber(N))
# This code is contributed by ita_c
// C# program to print the smallest
// integer not less than N with all odd digits
using System;
public class GFG{
// function to return the smallest number
// with all digits odd
static int smallestNumber(int n) {
int num = 0;
String s = "";
int duplicate = n;
// convert the number to string to
// perform operations
while (n > 0) {
s = (char) (n % 10 + 48) + s;
n /= 10;
}
int index = -1;
// find out the first even number
for (int i = 0; i < s.Length; i++) {
int digit = s[i] - '0';
if ((digit & 1) == 0) {
index = i;
break;
}
}
// if no even numbers are there, than n is the answer
if (index == -1) {
return duplicate;
}
// add all digits till first even
for (int i = 0; i < index; i++) {
num = num * 10 + (s[i] - '0');
}
// increase the even digit by 1
num = num * 10 + (s[index] - '0' + 1);
// add 1 to the right of the even number
for (int i = index + 1; i < s.Length; i++) {
num = num * 10 + 1;
}
return num;
}
// Driver Code
static public void Main() {
int N = 2397;
Console.WriteLine(smallestNumber(N));
}
}
// This code is contributed by PrinciRaj1992
<script>
// Javascript program to print the smallest
// integer not less than N with all odd digits
// function to return the smallest number
// with all digits odd
function smallestNumber(n)
{
var num = 0;
var s = "";
var duplicate = n;
// convert the number to string to
// perform operations
while (n) {
s = String.fromCharCode(n % 10 + 48) + s;
n = parseInt(n/10);
}
var index = -1;
// find out the first even number
for (var i = 0; i < s.length; i++) {
var digit = s[i].charCodeAt(0) - '0'.charCodeAt(0);
if ((digit & 1) == 0) {
index = i;
break;
}
}
// if no even numbers are there, than n is the answer
if (index == -1)
return duplicate;
// add all digits till first even
for (var i = 0; i < index; i++)
num = num * 10 + (s[i].charCodeAt(0) - '0'.charCodeAt(0));
// increase the even digit by 1
num = num * 10 + (s[index].charCodeAt(0) - '0'.charCodeAt(0) + 1);
// add 1 to the right of the even number
for (var i = index + 1; i < s.length; i++)
num = num * 10 + 1;
return num;
}
// Driver Code
var N = 2397;
document.write( smallestNumber(N));
</script>
Time Complexity: O(M), where M is the number of digits in N.
Auxiliary Space: O(M)
Another Approach:
Initialize a variable num to n.
If num is even, increment it by 1.
While num contains even digits:
a. Convert num to a string and check each digit.
b. If the current digit is even, add a power of 10 to num such that the resulting number has the same number of digits as num.
Return num.
C++
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n = 123456;
int num = n;
// If num is even, increment it by 1
if (num % 2 == 0) {
num++;
}
// While num contains even digits,
// add a power of 10 to num such that the resulting
// number
// has the same number of digits as num
while (1) {
int contains_even = 0;
string str = to_string(num);
int len = str.length();
for (int i = 0; i < len; i++) {
if ((str[i] - '0') % 2 == 0) {
contains_even = 1;
int pow10 = 1;
for (int j = 0; j < len - i - 1; j++) {
pow10 *= 10;
}
num += pow10;
break;
}
}
if (!contains_even) {
break;
}
}
cout << "Smallest odd digits number not less than " << n
<< " is: " << num << endl;
return 0;
}
// this code is contributed by thebeginner01(Akash Bankar)
#include <stdio.h>
#include <string.h>
int main()
{
int n = 123456;
int num = n;
// If num is even, increment it by 1
if (num % 2 == 0) {
num++;
}
// While num contains even digits, add a power of 10 to
// num such that the resulting number has the same
// number of digits as num
while (1) {
int contains_even = 0;
char str[20];
sprintf(str, "%d", num);
int len = strlen(str);
for (int i = 0; i < len; i++) {
if ((str[i] - '0') % 2 == 0) {
contains_even = 1;
int pow10 = 1;
for (int j = 0; j < len - i - 1; j++) {
pow10 *= 10;
}
num += pow10;
break;
}
}
if (!contains_even) {
break;
}
}
printf("Smallest odd digits number not less than %d "
"is: %d\n",
n, num);
return 0;
}
# Function to get the smallest odd digits number not less than n
def GetSmallestOddDigitsNumber(n):
num = n
# If num is even, increment it by 1
if num % 2 == 0:
num += 1
# While num contains even digits,
# add a power of 10 to num such that the resulting number
# has the same number of digits as num
while True:
contains_even = False
str_num = str(num)
len_num = len(str_num)
for i in range(len_num):
if int(str_num[i]) % 2 == 0:
contains_even = True
pow10 = 1
for j in range(len_num - i - 1):
pow10 *= 10
num += pow10
break
if not contains_even:
break
print("Smallest odd digits number not less than", n, "is:", num)
# Example usage
GetSmallestOddDigitsNumber(123456)
let n = 123456;
let num = n;
// If num is even, increment it by 1
if (num % 2 == 0) {
num++;
}
// While num contains even digits, add a power of 10 to num
// such that the resulting number has the same number of digits as num
while (1) {
let contains_even = 0;
let str = num.toString();
let len = str.length;
for (let i = 0; i < len; i++) {
if ((str[i] - '0') % 2 == 0) {
contains_even = 1;
let pow10 = 1;
for (let j = 0; j < len - i - 1; j++) {
pow10 *= 10;
}
num += pow10;
break;
}
}
if (!contains_even) {
break;
}
}
console.log("Smallest odd digits number not less than " + n + " is: " + num);
import java.io.*;
import java.lang.*;
import java.util.*;
class Main {
public static void main(String[] args)
throws java.lang.Exception
{
int n = 123456;
int num = n;
// If num is even, increment it by 1
if (num % 2 == 0) {
num++;
}
// While num contains even digits,
// add a power of 10 to num such that the resulting
// number
// has the same number of digits as num
while (true) {
int contains_even = 0;
String str = Integer.toString(num);
int len = str.length();
for (int i = 0; i < len; i++) {
if ((str.charAt(i) - '0') % 2 == 0) {
contains_even = 1;
int pow10 = 1;
for (int j = 0; j < len - i - 1; j++) {
pow10 *= 10;
}
num += pow10;
break;
}
}
if (contains_even == 0) {
break;
}
}
System.out.println(
"Smallest odd digits number not less than " + n
+ " is: " + num);
}
}
using System;
public class Program {
public static void Main()
{
int n = 123456;
int num = n;
// If num is even, increment it by 1
if (num % 2 == 0) {
num++;
}
// While num contains even digits,
// add a power of 10 to num such that the resulting
// number has the same number of digits as num
while (true) {
bool contains_even = false;
string str = num.ToString();
int len = str.Length;
for (int i = 0; i < len; i++) {
if ((str[i] - '0') % 2 == 0) {
contains_even = true;
int pow10 = 1;
for (int j = 0; j < len - i - 1; j++) {
pow10 *= 10;
}
num += pow10;
break;
}
}
if (!contains_even) {
break;
}
}
Console.WriteLine(
"Smallest odd digits number not less than " + n
+ " is: " + num);
}
}
OutputSmallest odd digits number not less than 123456 is: 133557
time complexity of O(log N) , Where N is given in the problem statement
space complexity of O(1)
Similar Reads
Smallest even digits number not less than N
Given a number N, we need to write a program to find the smallest number not less than N, which has all digits even. Examples: Input: N = 1345 Output: 2000Explanation: 2000 is the smallest number not less than N, whose all digits are even. Input : N = 2397Output : 2400 Explanation: 2400 is the small
15+ min read
Smallest odd number with N digits
Given a number N. The task is to find the smallest N digit ODD number.Examples: Input: N = 1 Output: 1 Input: N = 3 Output: 101 Approach: There can be two cases depending on the value of N. Case 1 : If N = 1 then answer will be 1. Case 2 : If N != 1 then answer will be (10^(n-1)) + 1 because the ser
3 min read
Smallest Even number with N digits
Given a number N, the task is to find the smallest Even number with N digits.Examples: Input: N = 1 Output: 0 Input: N = 2 Output: 10 Approach: Case 1 : If N = 1 then answer will be 0. Case 2 : if N != 1 then answer will be (10^(N-1)) because the series of smallest even numbers will go on like, 0, 1
3 min read
Smallest number not less than N which is divisible by all digits of N
Given a positive integer N, the task is to find the smallest integer greater than or equal to X, having all its digits divisible by the non-zero digits of N. Examples: Input: N = 280Output: 280Explanation:280 is the smallest which is divisible by the digits 8 and 2. Input: N = 32Output: 36Explanatio
5 min read
What is the smallest 4 digit number?
The method to represent and work with numbers is known as the number system. A number system is a system of writing to represent numbers. It is the mathematical notation used to represent numbers of a given set by using digits or other symbols. It has arithmetic operations to perform division, multi
5 min read
Smallest N digit number divisible by N
Given a positive integers N, the task is to find the smallest N digit number divisible by N. Examples: Input: N = 2 Output: 10 Explanation: 10 is the smallest 2-digit number which is divisible by 2. Input: N = 3 Output: 102 Explanation: 102 is the smallest 3-digit number which is divisible by 3. Nai
6 min read
Largest and Smallest N-digit Octal Numbers
Given an integer N, the task is to find the smallest and largest N-digit numbers in Octal Number System. Examples: Input: N = 4 Output: Largest: 7777 Smallest: 1000 Input: N = 2 Output: Largest: 77 Smallest: 10 Approach: The following steps can be followed to compute the required answer: Largest Num
5 min read
Smallest number greater than K by removing digits from N
Given two integers N and K (K<N), the task is to find the smallest number greater than K by removing digits from N. Note: You cannot rearrange the digits of N. Examples: Input: N = 7182, K = 11Output: 12Explanation: Among all the possible combination, 12 is minimum number greater than 11. Input:
13 min read
Smallest N digit number which is a multiple of 5
Given an integer N ? 1, the task is to find the smallest N digit number which is a multiple of 5.Examples: Input: N = 1 Output: 5Input: N = 2 Output: 10 Input: N = 3 Output: 100 Approach: If N = 1 then the answer will be 5.If N > 1 then the answer will be (10(N - 1)) because the series of smalles
3 min read
Find the smallest number whose sum of digits is N
Given a positive integers N, the task is to find the smallest number whose sum of digits is N.Example: Input: N = 10Output: 19Explanation: 1 + 9 = 10 = N Input: N = 18Output: 99Explanation: 9 + 9 = 18 = N Naive Approach: A Naive approach is to run a loop of i starting from 0 and find Sum of digits o
6 min read