Рубрики

Наибольшее число не больше N, все цифры которого нечетные

Учитывая число N , задача состоит в том, чтобы найти наибольшее число, не превышающее N, в котором все его цифры являются нечетными .

Примеры:

Input: N = 23
Output: 19
19 is the largest number less than 23 which has all odd digits.

Input: N = 7236
Output: 7199

Наивный подход : выполните итерацию от N до 0 и найдите первое число со всеми его цифрами как нечетное. Этот подход все еще можно оптимизировать, если пропустить четные числа, поскольку каждое четное число будет иметь четную цифру справа.

Ниже приведена реализация вышеуказанного подхода:

C ++

// Программа CPP для печати наибольшего целого числа
// не больше N со всеми нечетными цифрами
#include <bits/stdc++.h>

using namespace std;

  
// Функция проверки всех цифр
// числа нечетные

bool allOddDigits(int n)

{

    // итерация для всех цифр

    while (n) {

  

        // если цифра четная

        if ((n % 10) % 2 == 0)

            return false;

        n /= 10;

    }

  

    // все цифры нечетные

    return true;

}

  
// функция для возврата наибольшего числа
// со всеми нечетными цифрами

int largestNumber(int n)

{

    if (n % 2 == 0)

        n--;

  

    // итерация, пока мы не найдем

    // номер со всеми нечетными цифрами

    for (int i = n;; i -= 2)

        if (allOddDigits(i))

            return i;

}

  
// Код драйвера

int main()

{

    int N = 23;

    cout << largestNumber(N);

    return 0;

}

Джава

// Java-программа для печати наибольшего целого числа
// не больше N со всеми нечетными цифрами

  

public class GFG{

  

        // Функция проверки всех цифр

        // числа нечетные

        static boolean allOddDigits(int n) 

        

            // итерация для всех цифр

            while (n != 0) { 

            

                // если цифра четная

                if ((n % 10) % 2 == 0

                    return false

                n /= 10

            

            

            // все цифры нечетные

            return true

        

            

        // функция для возврата наибольшего числа

        // со всеми нечетными цифрами

        static int largestNumber(int n) 

        

            if (n % 2 == 0

                n--; 

            

            // итерация, пока мы не найдем

            // номер со всеми нечетными цифрами

            for (int i = n;; i -= 2

                if (allOddDigits(i)) 

                    return i; 

        

  

     public static void main(String []args){

           

        int N = 23

        System.out.println(largestNumber(N));

   

    }

    // Этот код предоставлен ANKITRAI1

       
}

python3

# Программа Python 3 для печати самой большой
# целое число не больше чем N со всеми
# нечетные цифры

  
# Функция, чтобы проверить, все ли цифры
№ числа нечетные

def allOddDigits(n):

      

    # повторять для всех цифр

    while (n):

  

        # если цифра четная

        if ((n % 10) % 2 == 0):

            return False

        n = int(n / 10)

  

    # все цифры нечетные

    return True

  
# функция для возврата наибольшего
# номер со всеми нечетными цифрами

def largestNumber(n):

    if (n % 2 == 0):

        n -= 1

  

    # итерации, пока мы не найдем

    # номер со всеми нечетными цифрами

    i = n

    while(1):

        if (allOddDigits(i)):

            return i

        i -= 2

  
Код водителя

if __name__ =='__main__':

    N = 23

    print(largestNumber(N))

      
# Этот код предоставлен
# Shashank_Sharma

C #

// C # программа для печати самой большой
// целое число не больше чем N с
// все нечетные цифры

using System;

  

class GFG

{

  
// Функция для проверки, если все
// цифры номера нечетные

static bool allOddDigits(int n) 

    // итерация для всех цифр

    while (n != 0) 

    

  

        // если цифра четная

        if ((n % 10) % 2 == 0) 

            return false

        n /= 10; 

    

  

    // все цифры нечетные

    return true

  
// функция для возврата наибольшего
// номер со всеми нечетными цифрами

static int largestNumber(int n) 

    if (n % 2 == 0) 

        n--; 

  

    // итерация, пока мы не найдем

    // номер со всеми нечетными цифрами

    for (int i = n;; i -= 2) 

        if (allOddDigits(i)) 

            return i; 

  
// Код драйвера

public static void Main()

{

    int N = 23; 

  

    Console.WriteLine(largestNumber(N));

}
}

  
// Этот код предоставлен anuj_67

PHP

<?php
// PHP программа для вывода наибольшего целого числа
// не больше N со всеми нечетными цифрами

  
// Функция проверки всех цифр
// числа нечетные

function allOddDigits($n)

{

    // итерация для всех цифр

    while ($n > 1) 

    {

  

        // если цифра четная

        if (($n % 10) % 2 == 0)

            return false;

        $n = (int)$n / 10;

    }

  

    // все цифры нечетные

    return true;

}

  
// функция для возврата наибольшего
// номер со всеми нечетными цифрами

function largestNumber($n)

{

    if ($n % 2 == 0)

        $n--;

  

    // итерация, пока мы не найдем

    // номер со всеми нечетными цифрами

    for ($i = $n;; $i= ($i - 2))

        if (allOddDigits($i))

            return $i;

}

  
// Код драйвера

$N = 23;

echo largestNumber($N);

  
// Этот код предоставлен ajit
?>

Выход:

19

Сложность времени: O (N)

Эффективный подход: мы можем получить требуемое число, уменьшив первую четную цифру в N на одну, а затем заменив все остальные цифры наибольшей нечетной цифрой, т.е. 9 . Например, если N = 24578, то X = 19999 . Если в N нет четных цифр, то N — это само число.

Ниже приведена реализация вышеуказанного подхода:

C ++

// Программа CPP для печати наибольшего целого числа
// не больше N со всеми нечетными цифрами
#include <bits/stdc++.h>

using namespace std;

  
// функция для возврата наибольшего числа
// со всеми нечетными цифрами

int largestNumber(int n)

{

    string s = "";

    int duplicate = n;

  

    // преобразовать число в строку для

    // простые операции

    while (n) {

        s = char(n % 10 + 48) + s;

        n /= 10;

    }

  

    int index = -1;

  

    // найти первую четную цифру

    for (int i = 0; i < s.length(); i++) {

        if (((s[i] - '0') % 2 & 1) == 0) {

            index = i;

            break;

        }

    }

  

    // если четной цифры нет, то N - ответ

    if (index == -1)

        return duplicate;

  

    int num = 0;

  

    // до первой четной цифры, добавить все нечетные числа

    for (int i = 0; i < index; i++)

        num = num * 10 + (s[i] - '0');

  

    // уменьшить 1 от четной цифры

    num = num * 10 + (s[index] - '0' - 1);

  

    // добавляем 9 в остальные цифры

    for (int i = index + 1; i < s.length(); i++)

        num = num * 10 + 9;

  

    return num;

}

  
// Код драйвера

int main()

{

    int N = 24578;

  

    cout << largestNumber(N);

  

    return 0;

}

Джава

// Java-программа для печати наибольшего целого числа
// не больше N со всеми нечетными цифрами

  

class GFG

{

      
// функция для возврата наибольшего числа
// со всеми нечетными цифрами

static int largestNumber(int n)

{

    String s = "";

    int duplicate = n;

  

    // преобразовать число в строку для

    // простые операции

    while (n > 0

    {

        s = (char)(n % 10 + 48) + s;

        n /= 10;

    }

  

    int index = -1;

  

    // найти первую четную цифру

    for (int i = 0; i < s.length(); i++) 

    {

        if (((int)(s.charAt(i) - '0') % 2 & 1) == 0

        {

            index = i;

            break;

        }

    }

  

    // если четной цифры нет, то N - ответ

    if (index == -1)

        return duplicate;

  

    int num = 0;

  

    // до первой четной цифры, добавить все нечетные числа

    for (int i = 0; i < index; i++)

        num = num * 10 + (int)(s.charAt(i) - '0');

  

    // уменьшить 1 от четной цифры

    num = num * 10 + ((int)s.charAt(index) - (int)('0') - 1);

  

    // добавляем 9 в остальные цифры

    for (int i = index + 1; i < s.length(); i++)

        num = num * 10 + 9;

  

    return num;

}

  
// Код драйвера

public static void main (String[] args) 

{

    int N = 24578;

  

    System.out.println(largestNumber(N));

}
}

  
// Этот код предоставлен mits

python3

# Python3 программа для вывода наибольшего целого числа
# не больше N со всеми нечетными цифрами

  
# функция для возврата наибольшего числа
# со всеми нечетными цифрами

def largestNumber(n):

  

    s = ""

    duplicate = n

  

    # преобразовать число в строку для

    # простые операции

    while (n):

        s = chr(n % 10 + 48) + s

        n //= 10

  

    index = -1

  

    # найти первую четную цифру

    for i in range(len(s)):

        if (((ord(s[i]) -

              ord('0')) % 2 & 1) == 0):

            index = i

            break

          

    # если нет четной цифры, то N является ответом

    if (index == -1):

        return duplicate

  

    num = 0

  

    # до первой четной цифры,

    # добавить все нечетные числа

    for i in range(index):

        num = num * 10 + (ord(s[i]) - ord('0'))

  

    # уменьшить 1 от четной цифры

    num = num * 10 + (ord(s[index]) - 

                      ord('0') - 1)

  

    # добавить 9 в остальные цифры

    for i in range(index + 1, len(s)):

        num = num * 10 + 9

  

    return num

  
Код водителя

N = 24578

print(largestNumber(N))

  
# Этот код предоставлен Мохит Кумар

C #

// C # программа для вывода наибольшего целого числа
// не больше N со всеми нечетными цифрами

using System;

  

class GFG

{

      
// функция для возврата наибольшего числа
// со всеми нечетными цифрами

static int largestNumber(int n)

{

    string s = "";

    int duplicate = n;

  

    // преобразовать число в строку для

    // простые операции

    while (n > 0) 

    {

        s = (char)(n % 10 + 48) + s;

        n /= 10;

    }

  

    int index = -1;

  

    // найти первую четную цифру

    for (int i = 0; i < s.Length; i++) 

    {

        if (((int)(s[i] - '0') % 2 & 1) == 0) 

        {

            index = i;

            break;

        }

    }

  

    // если четной цифры нет, то N - ответ

    if (index == -1)

        return duplicate;

  

    int num = 0;

  

    // до первой четной цифры, добавить все нечетные числа

    for (int i = 0; i < index; i++)

        num = num * 10 + (int)(s[i] - '0');

  

    // уменьшить 1 от четной цифры

    num = num * 10 + ((int)s[index] - (int)('0') - 1);

  

    // добавляем 9 в остальные цифры

    for (int i = index + 1; i < s.Length; i++)

        num = num * 10 + 9;

  

    return num;

}

  
// Код драйвера

static void Main()

{

    int N = 24578;

  

    Console.WriteLine(largestNumber(N));

}
}

  
// Этот код предоставлен mits

Выход:

19999

Сложность времени: O (M) где M — количество цифр

Рекомендуемые посты:

Наибольшее число не больше N, все цифры которого нечетные

0.00 (0%) 0 votes