Рубрики

Найти следующий редкий номер

Число является разреженным, если в его двоичном представлении нет двух смежных единиц. Например, 5 (двоичное представление: 101) является разреженным, но 6 (двоичное представление: 110) не является разреженным.
Учитывая число x, найдите наименьшее разреженное число, которое больше или равно x.

Примеры:

Input: x = 6
Output: Next Sparse Number is 8

Input: x = 4
Output: Next Sparse Number is 4

Input: x = 38
Output: Next Sparse Number is 40

Input: x = 44
Output: Next Sparse Number is 64

Мы настоятельно рекомендуем вам нажать здесь и попрактиковаться, прежде чем переходить к решению.

Простое решение заключается в следующем:

1) Write a utility function isSparse(x) that takes a number 
   and returns true if x is sparse, else false.  This function
   can be easily written by traversing the bits of input number.
2) Start from x and do following 
   while(1)
   {
      if (isSparse(x))
         return x;
      else 
         x++
   }

Временная сложность isSparse () равна O (Log x). Временная сложность этого решения составляет O (x Log x). Следующее разреженное число может быть на расстоянии не более O (x).

Спасибо kk_angel за предложенное решение.

Эффективное решение может решить эту проблему, не проверяя все числа по одному. Ниже приведены шаги.

1) Find binary of the given number and store it in a 
   boolean array.
2) Initialize last_finalized bit position as 0.
2) Start traversing the binary from least significant bit.
    a) If we get two adjacent 1's such that next (or third) 
       bit is not 1, then 
          (i)  Make all bits after this 1 to last finalized
               bit (including last finalized) as 0. 
          (ii) Update last finalized bit as next bit. 

Например, пусть двоичное представление будет 010100010 11 101, мы изменим его на 01010001 100000 (все биты после выделенного 11 установлены в 0). Снова две единицы смежны, поэтому измените двоичное представление на 010100 10000000 . Это наш окончательный ответ.

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

C ++

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

using namespace std;

  

int nextSparse(int x)

{

    // Найти двоичное представление x и сохранить его в bin [].

    // bin [0] содержит младший значащий бит (LSB), следующий

    // бит находится в bin [1] и так далее.

    vector<bool> bin;

    while (x != 0)

    {

        bin.push_back(x&1);

        x >>= 1;

    }

  

    // Там может быть дополнительный бит в результате, поэтому добавьте один дополнительный бит

    bin.push_back(0);

    int n = bin.size();  // Размер двоичного представления

  

    // Позиция, до которой завершаются все биты

    int last_final = 0;

  

    // Начало со второго бита (рядом с LSB)

    for (int i=1; i<n-1; i++)

    {

       // Если текущий бит и его предыдущий бит равны 1, но следующий

       // бит не равен 1.

       if (bin[i] == 1 && bin[i-1] == 1 && bin[i+1] != 1)

       {

            // Сделать следующий бит 1

            bin[i+1] = 1;

  

            // Сделать все биты перед текущим битом равными 0, чтобы сделать

            // уверен, что мы получим наименьшее следующее число

            for (int j=i; j>=last_final; j--)

                bin[j] = 0;

  

            // Сохраняем позицию бита, установленного так, чтобы этот бит

            // и биты перед этим не будут изменены в следующий раз.

            last_final = i+1;

        }

    }

  

    // Найти десятичный эквивалент модифицированного bin []

    int ans = 0;

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

        ans += bin[i]*(1<<i);

    return ans;

}

  
// Драйвер программы

int main()

{

    int x = 38;

    cout << "Next Sparse Number is " << nextSparse(x);

    return 0;

}

Джава

// Java программа для поиска следующего разреженного числа

import java.util.*; 

  

class GFG{

static int nextSparse(int x) 

    // Найти двоичное представление x и сохранить его в bin.get (].

    // bin.get (0] содержит младший бит (LSB), следующий

    // бит находится в bin.get (1] и так далее.

    ArrayList<Integer> bin = new ArrayList<Integer>(); 

    while (x != 0

    

        bin.add(x&1); 

        x >>= 1

    

  

    // Там может быть дополнительный бит в результате, поэтому добавьте один дополнительный бит

    bin.add(0); 

    int n = bin.size(); // Размер двоичного представления

  

    // Позиция, до которой завершаются все биты

    int last_final = 0

  

    // Начало со второго бита (рядом с LSB)

    for (int i=1; i<n-1; i++) 

    

    // Если текущий бит и его предыдущий бит равны 1, но следующий

    // бит не равен 1.

    if (bin.get(i) == 1 && bin.get(i-1) == 1 && bin.get(i+1) != 1

    

            // Сделать следующий бит 1

            bin.set(i+1,1); 

  

            // Сделать все биты перед текущим битом равными 0, чтобы сделать

            // уверен, что мы получим наименьшее следующее число

            for (int j=i; j>=last_final; j--) 

                bin.set(j,0); 

  

            // Сохраняем позицию бита, установленного так, чтобы этот бит

            // и биты перед этим не будут изменены в следующий раз.

            last_final = i+1

        

    

  

    // Найти десятичный эквивалент модифицированного bin.get (]

    int ans = 0

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

        ans += bin.get(i)*(1<<i); 

    return ans; 

  
// Драйвер программы

public static void main(String[] args) 

    int x = 38

    System.out.println("Next Sparse Number is "+nextSparse(x));


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

python3

# Python3 программа для поиска следующего
# редкое число

  

def nextSparse(x):

      

    # Найти двоичное представление

    # x и сохранить его в bin [].

    # bin [0] содержит наименее значимый

    # бит (LSB), следующий бит в бине [1],

    # и так далее.

    bin = [] 

    while (x != 0):

        bin.append(x & 1

        x >>= 1

  

    # Там может быть дополнительный бит в результате,

    # так что добавьте еще один бит

    bin.append(0

    n = len(bin) # Размер двоичного представления

      

    # Позиция до которой все

    # биты завершены

    last_final = 0

  

    # Начать со второго бита (рядом с LSB)

    for i in range(1,n - 1):

          

        # Если текущий бит и его предыдущий

        # бит равен 1, но следующий бит не равен 1.

        if ((bin[i] == 1 and bin[i - 1] == 1 

            and bin[i + 1] != 1)):

                  

            # Сделать следующий бит 1

            bin[i + 1] = 1 

              

            # Сделать все биты до текущего

            # бит 0, чтобы убедиться, что

            # получаем следующее наименьшее число

            for j in range(i,last_final-1,-1):

                bin[j] = 0

              

            # Сохранение позиции набора битов

            # так что это бит

            # до того, как он не будет изменен в следующий раз.

            last_final = i + 1 

  

    # Найти десятичный эквивалент

    # измененного бина []

    ans = 0 

    for i in range(n): 

        ans += bin[i] * (1 << i) 

    return ans 

  
Код водителя

if __name__=='__main__':

    x = 38 

    print("Next Sparse Number is",nextSparse(x)) 

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

C #

// C # программа для поиска следующего разреженного числа

using System;

using System.Collections;

  

  

class GFG{

static int nextSparse(int x) 

    // Найти двоичное представление x и сохранить его в bin.get (].

    // bin.get (0] содержит младший бит (LSB), следующий

    // бит находится в bin.get (1] и так далее.

    ArrayList bin = new ArrayList(); 

    while (x != 0) 

    

        bin.Add(x&1); 

        x >>= 1; 

    

  

    // Там может быть дополнительный бит в результате, поэтому добавьте один дополнительный бит

    bin.Add(0); 

    int n = bin.Count; // Размер двоичного представления

  

    // Позиция, до которой завершаются все биты

    int last_final = 0; 

  

    // Начало со второго бита (рядом с LSB)

    for (int i = 1; i < n-1; i++) 

    

    // Если текущий бит и его предыдущий бит равны 1, но следующий

    // бит не равен 1.

    if ((int)bin[i] == 1 && (int)bin[i-1] == 1 && (int)bin[i+1] != 1) 

    

            // Сделать следующий бит 1

            bin[i+1]=1; 

  

            // Сделать все биты перед текущим битом равными 0, чтобы сделать

            // уверен, что мы получим наименьшее следующее число

            for (int j = i; j >= last_final; j--) 

                bin[j]=0; 

  

            // Сохраняем позицию бита, установленного так, чтобы этот бит

            // и биты перед этим не будут изменены в следующий раз.

            last_final = i + 1; 

        

    

  

    // Найти десятичный эквивалент модифицированного bin.get (]

    int ans = 0; 

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

        ans += (int)bin[i]*(1<<i); 

    return ans; 

  
// Драйвер программы

static void Main() 

    int x = 38; 

    Console.WriteLine("Next Sparse Number is "+nextSparse(x));


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

PHP

<?php
// PHP программа для поиска следующего разреженного числа

  

function nextSparse($x)

{

    // Найти двоичное представление

    // х и сохранить его в bin [].

    // bin [0] содержит наименее значимый

    // бит (LSB), следующий бит в бине [1],

    // и так далее.

    $bin = array();

    while ($x != 0)

    {

        array_push($bin, $x & 1);

        $x >>= 1;

    }

  

    // Там может быть дополнительный бит в результате,

    // добавим еще один бит

    array_push($bin, 0);

    $n = count($bin); // Размер двоичного представления

      

    // Позиция до которой все

    // биты завершены

    $last_final = 0;

  

    // Начало со второго бита (рядом с LSB)

    for ($i = 1; $i < $n - 1; $i++)

    {

    // Если текущий бит и его предыдущий

    // бит равен 1, но следующий бит не равен 1.

    if ($bin[$i] == 1 && 

        $bin[$i - 1] == 1 && 

        $bin[$i + 1] != 1)

    {

        // Сделать следующий бит 1

        $bin[$i + 1] = 1;

  

        // Сделать все биты до текущего

        // бит 0, чтобы убедиться, что

        // получаем следующее наименьшее число

        for ($j = $i; $j >= $last_final; $j--)

            $bin[$j] = 0;

  

        // Сохраняем позицию установленного бита

        // чтобы этот бит

        // до того, как оно не будет изменено в следующий раз.

        $last_final = $i + 1;

    }

    }

  

    // Найти десятичный эквивалент

    // модифицированного бина []

    $ans = 0;

    for ($i = 0; $i < $n; $i++)

        $ans += $bin[$i] * (1 << $i);

    return $ans;

}

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

$x = 38;

echo "Next Sparse Number is "

                nextSparse($x);

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


Выход:

Next Sparse Number is 40

Временная сложность этого решения составляет O (Log x).

Спасибо gccode за предложенное выше решение.

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

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

Найти следующий редкий номер

0.00 (0%) 0 votes