Рубрики

Ближайшее большее число, меняя цифры

Даны два целых числа А и В. Задача состоит в том, чтобы найти ближайшее большее значение для B , чередуя цифры A. Если такая перестановка невозможна, выведите -1.

Примеры:

Input: A = 459, B = 500
Output: 549
549 is the nearest greater.

Input: A = 321, B = 567
Output: -1

Input: A = 231, B = 125
Output: 132

Предпосылки: Все перестановки строки

Подходить:

  • Установите минимальное значение min1, используя Integer.MAX_VALUE
  • Поменяйте местами цифру A, используя вышеупомянутый метод перестановки.
  • Проверьте, является ли перестановка A меньше min1 или нет. Если меньше, тогда обновите min1 как A.
  • Повторите это для всех перестановок A и найдите минимальное большее значение

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

C ++

// C ++ программа для поиска ближайшего большего значения
#include <bits/stdc++.h>

using namespace std;

  

int min1 = INT_MAX;

int _count = 0;

  
// Найти все возможные перестановки значения A.

int permutation(string str1, int i, int n, int p)

{

    if (i == n)

    {

        // Конвертировать в целое число

        int q = stoi(str1);

  

        // Находим минимальное значение A путем обмена

        // цифра A и сохранение min1.

        if (q - p > 0 && q < min1)

        {

            min1 = q;

            _count = 1;

        }

    }

    else

    {

        for (int j = i; j <= n; j++)

        {

            // Поменять местами два строковых символа

            swap(str1[i], str1[j]);

            permutation(str1, i + 1, n, p);

            swap(str1[i], str1[j]);

        }

    }

    return min1;

}

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

int main()

{

    int A = 213;

    int B = 111;

  

    // Преобразуем целочисленное значение в строку в

    // найти всю перестановку числа

    string str1 = to_string(A);

    int len = str1.length();

    int h = permutation(str1, 0, len - 1, B);

  

    // count = 1 означает, что число больше B существует

    _count ? cout << h << endl : cout << -1 << endl;

  

    return 0;

}

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

Джава

// JAVA-программа для поиска ближайшего большего значения

import java.io.*;

import java.util.*;

  

class GFG {

    static int min1 = Integer.MAX_VALUE;

    static int count = 0;

  

    // Найти все возможные перестановки значения A.

    public int permutation(String str1, int i, int n, int p)

    {

  

        if (i == n) {

  

            // Конвертировать в целое число

            int q = Integer.parseInt(str1);

  

            // Находим минимальное значение A путем обмена

            // цифра A и сохранение min1.

            if (q - p > 0 && q < min1) {

                min1 = q;

                count = 1;

            }

        }

  

        else {

            for (int j = i; j <= n; j++) {

                str1 = swap(str1, i, j);

                permutation(str1, i + 1, n, p);

                str1 = swap(str1, i, j);

            }

        }

        return min1;

    }

  

    // Поменять местами два строковых символа

    public String swap(String str, int i, int j)

    {

        char ch[] = str.toCharArray();

        char temp = ch[i];

        ch[i] = ch[j];

        ch[j] = temp;

        // Возвращаем строку после

        // переключение между двумя символами.

        return String.valueOf(ch);

    }

  

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

    public static void main(String[] args)

    {

  

        int A = 213;

        int B = 111;

  

        GFG gfg = new GFG();

  

        // Преобразуем целочисленное значение в строку в

        // найти всю перестановку числа

        String str1 = Integer.toString(A);

        int len = str1.length();

        int h = gfg.permutation(str1, 0, len - 1, B);

  

        // count = 1 означает, что число больше B существует

        if (count == 1)

            System.out.println(h);

        else

            System.out.println(-1);

    }

}

python3

# Python3 программа для поиска ближайшего большего значения

min1 = 10**9

_count = 0

  
# Найти все возможные перестановки значения А.

def permutation(str1, i, n, p):

    global min1, _count

    if (i == n):

          

        # Преобразовать в целое число

        str1 = "".join(str1)

        q = int(str1)

  

        # Найти минимальное значение A

        # путем замены цифр

        № А и магазин мин1.

        if (q - p > 0 and q < min1):

            min1 = q

            _count = 1

    else:

        for j in range(i, n + 1):

              

            # Поменяйте местами два символа)

            str1[i], str1[j] = str1[j], str1[i]

            permutation(str1, i + 1, n, p)

            str1[i], str1[j] = str1[j], str1[i]

  

    return min1

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

A = 213

B = 111

  
# Преобразовать целочисленное значение в
# найти все перестановки числа

str2 = str(A)

str1 = [i for i in str2]

le = len(str1)

  

h = permutation(str1, 0, le - 1, B)

  
# count = 1 означает, что число больше B существует

if _count == 1:

    print(h)

else:

    print(-1)

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

C #

// C # программа для поиска ближайшего большего значения

using System;

      

class GFG

{

    static int min1 = int.MaxValue;

    static int count = 0;

  

    // Найти все возможные перестановки значения A.

    public int permutation(String str1, int i, 

                                 int n, int p)

    {

        if (i == n) 

        {

  

            // Конвертировать в целое число

            int q = int.Parse(str1);

  

            // Находим минимальное значение A путем обмена

            // цифра A и сохранение min1.

            if (q - p > 0 && q < min1)

            {

                min1 = q;

                count = 1;

            }

        }

  

        else 

        {

            for (int j = i; j <= n; j++) 

            {

                str1 = swap(str1, i, j);

                permutation(str1, i + 1, n, p);

                str1 = swap(str1, i, j);

            }

        }

        return min1;

    }

  

    // Поменять местами два строковых символа

    public String swap(String str, int i, int j)

    {

        char []ch = str.ToCharArray();

        char temp = ch[i];

        ch[i] = ch[j];

        ch[j] = temp;

          

        // Возвращаем строку после

        // переключение между двумя символами.

        return String.Join("", ch);

    }

  

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

    public static void Main(String[] args)

    {

        int A = 213;

        int B = 111;

  

        GFG gfg = new GFG();

  

        // Преобразуем целочисленное значение в строку в

        // найти всю перестановку числа

        String str1 = A.ToString();

        int len = str1.Length;

        int h = gfg.permutation(str1, 0, len - 1, B);

  

        // count = 1 означает, что число больше B существует

        if (count == 1)

            Console.WriteLine(h);

        else

            Console.WriteLine(-1);

    }

}

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

Выход:

123

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

Ближайшее большее число, меняя цифры

0.00 (0%) 0 votes