Рубрики

Двоичное представление следующего большего числа с тем же числом 1 и 0

Учитывая двоичный вход, который представляет двоичное представление положительного числа n, найдите двоичное представление наименьшего числа больше чем n с тем же числом 1 и 0, что и в двоичном представлении n. Если такое число не может быть сформировано, выведите «no more number».

Двоичный вход может быть и может не помещаться даже в unsigned long long int.

Примеры:

Input : 10010
Output : 10100
Here n = (18)10 = (10010)2next greater = (20)10 = (10100)2
Binary representation of 20 contains same number of
1's and 0's as in 18.

Input : 111000011100111110
Output :  111000011101001111

Эта проблема просто сводится к поиску следующей перестановки данной строки. Мы можем найти next_permutation () входного двоичного числа.

Ниже приведен алгоритм поиска следующей перестановки в двоичной строке.

  1. Пройдите двоичную строку bstr справа.
  2. При прохождении найдите первый индекс i такой, что bstr [i] = '0' и bstr [i + 1] = '1'.
  3. Обменный символ по индексам «i» и «i + 1».
  4. Поскольку нам нужно наименьшее следующее значение, рассмотрим подстроку от индекса i + 2 до конца и переместим все 1 в подстроке в конце.

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

C ++

// C ++ программа для поиска следующей перестановки в
// двоичная строка.
#include <bits/stdc++.h>

using namespace std;

  
// Функция для поиска следующего большего числа
// с одинаковыми номерами 1 и 0
string nextGreaterWithSameDigits(string bnum)
{

    int l = bnum.size();

    int i;

    for (int i=l-2; i>=1; i--)

    {

        // найти первый 'i' от конца так, чтобы

        // bnum [i] == '0' и bnum [i + 1] == '1'

        // меняем эти значения и ломаем;

        if (bnum.at(i) == '0' &&

           bnum.at(i+1) == '1')

        {

            char ch = bnum.at(i);

            bnum.at(i) = bnum.at(i+1);

            bnum.at(i+1) = ch;

            break;

        }

    }

  

    // если обмен не выполнен

    if (i == 0)

        "no greater number";

  

    // Поскольку мы хотим наименьшее следующее значение,

    // сдвигаем все 1 в конце в двоичном

    // подстрока, начинающаяся с индекса 'i + 2'

    int j = i+2, k = l-1;

    while (j < k)

    {

        if (bnum.at(j) == '1' && bnum.at(k) == '0')

        {

            char ch = bnum.at(j);

            bnum.at(j) = bnum.at(k);

            bnum.at(k) = ch;

            j++;

            k--;

        }

  

        // особый случай при замене, если '0'

        // происходит, а затем перерыв

        else if (bnum.at(i) == '0')

            break;

  

        else

            j++;

  

    }

  

    // требуется следующий больший номер

    return bnum;

}

  
// Программа драйвера для тестирования выше

int main()

{

    string bnum = "10010";

    cout << "Binary representation of next greater number = "

         << nextGreaterWithSameDigits(bnum);

    return 0;

}

Джава

// Java-программа для поиска следующей перестановки в
// двоичная строка.

class GFG 

{

  
// Функция для поиска следующего большего числа
// с одинаковыми номерами 1 и 0

static String nextGreaterWithSameDigits(char[] bnum)

{

    int l = bnum.length;

    int i;

    for (i = l - 2; i >= 1; i--)

    {

        // найти первый 'i' от конца так, чтобы

        // bnum [i] == '0' и bnum [i + 1] == '1'

        // меняем эти значения и ломаем;

        if (bnum[i] == '0' &&

        bnum[i+1] == '1')

        {

            char ch = bnum[i];

            bnum[i] = bnum[i+1];

            bnum[i+1] = ch;

            break;

        }

    }

  

    // если обмен не выполнен

    if (i == 0)

        System.out.println("no greater number");

  

    // Поскольку мы хотим наименьшее следующее значение,

    // сдвигаем все 1 в конце в двоичном

    // подстрока, начинающаяся с индекса 'i + 2'

    int j = i + 2, k = l - 1;

    while (j < k)

    {

        if (bnum[j] == '1' && bnum[k] == '0')

        {

            char ch = bnum[j];

            bnum[j] = bnum[k];

            bnum[k] = ch;

            j++;

            k--;

        }

  

        // особый случай при замене, если '0'

        // происходит, а затем перерыв

        else if (bnum[i] == '0')

            break;

  

        else

            j++;

  

    }

  

    // требуется следующий больший номер

    return String.valueOf(bnum);

}

  
// Программа драйвера для тестирования выше

public static void main(String[] args)

{

    char[] bnum = "10010".toCharArray();

    System.out.println("Binary representation of next greater number = "

        + nextGreaterWithSameDigits(bnum));

}
}

  
// Этот код предоставлен Rajput-Ji

C #

// C # программа для поиска следующей перестановки в
// двоичная строка.

using System;

  

class GFG 

{

  
// Функция для поиска следующего большего числа
// с одинаковыми номерами 1 и 0

static String nextGreaterWithSameDigits(char[] bnum)

{

    int l = bnum.Length;

    int i;

    for (i = l - 2; i >= 1; i--)

    {

        // найти первый 'i' от конца так, чтобы

        // bnum [i] == '0' и bnum [i + 1] == '1'

        // меняем эти значения и ломаем;

        if (bnum[i] == '0' &&

        bnum[i+1] == '1')

        {

            char ch = bnum[i];

            bnum[i] = bnum[i+1];

            bnum[i+1] = ch;

            break;

        }

    }

  

    // если обмен не выполнен

    if (i == 0)

        Console.WriteLine("no greater number");

  

    // Поскольку мы хотим наименьшее следующее значение,

    // сдвигаем все 1 в конце в двоичном

    // подстрока, начинающаяся с индекса 'i + 2'

    int j = i + 2, k = l - 1;

    while (j < k)

    {

        if (bnum[j] == '1' && bnum[k] == '0')

        {

            char ch = bnum[j];

            bnum[j] = bnum[k];

            bnum[k] = ch;

            j++;

            k--;

        }

  

        // особый случай при замене, если '0'

        // происходит, а затем перерыв

        else if (bnum[i] == '0')

            break;

  

        else

            j++;

  

    }

  

    // требуется следующий больший номер

    return String.Join("",bnum);

}

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

public static void Main(String[] args)

{

    char[] bnum = "10010".ToCharArray();

    Console.WriteLine("Binary representation of next greater number = "

        + nextGreaterWithSameDigits(bnum));

}
}

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

Выход:

Binary representation of next greater number = 10100

Сложность времени: O (n), где n — количество бит на входе.

Эта статья предоставлена Аюшем Джаухари . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

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

Двоичное представление следующего большего числа с тем же числом 1 и 0

0.00 (0%) 0 votes