Рубрики

Проверьте, является ли номер Bleak

Число 'n' называется Bleak, если его нельзя представить в виде суммы положительного числа x и установить количество битов в x, то есть x + countSetBits (x) не равно n для любого неотрицательного числа x.

Примеры :

Input : n = 3
Output : false
3 is not Bleak as it can be represented
as 2 + countSetBits(2).

Input : n = 4
Output : true
4 is t Bleak as it cannot be represented 
as sum of a number x and countSetBits(x)
for any number x.

Способ 1 (простой)

bool isBleak(n)
1) Consider all numbers smaller than n
    a) If x + countSetBits(x) == n
           return false

2) Return true

Ниже приведена реализация простого подхода.

C ++

// Простая программа на C ++ для проверки Bleak Number
#include <bits/stdc++.h>

using namespace std;

  
/ * Функция, чтобы получить не из установленных битов в двоичном

   представление переданного двоичного кода * /

int countSetBits(int x)

{

    unsigned int count = 0;

    while (x) {

        x &= (x - 1);

        count++;

    }

    return count;

}

  
// Возвращает true, если n - Bleak

bool isBleak(int n)

{

    // Проверяем все числа 'x' меньше

    // чем п. Если x + countSetBits (x)

    // становится n, тогда n не может быть холодным

    for (int x = 1; x < n; x++)

        if (x + countSetBits(x) == n)

            return false;

  

    return true;

}

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

int main()

{

    isBleak(3) ? cout << "Yes\n" : cout << "No\n";

    isBleak(4) ? cout << "Yes\n" : cout << "No\n";

    return 0;

}

Джава

// Простая Java-программа для проверки Bleak Number

import java.io.*;

  

class GFG {

  

    / * Функция, чтобы получить не из установленных битов в двоичном

       представление переданного двоичного кода * /

    static int countSetBits(int x)

    {

        int count = 0;

        while (x != 0) {

            x &= (x - 1);

            count++;

        }

        return count;

    }

  

    // Возвращает true, если n - Bleak

    static boolean isBleak(int n)

    {

        // Проверяем все числа 'x' меньше

        // чем п. Если x + countSetBits (x)

        // становится n, тогда n не может быть холодным

        for (int x = 1; x < n; x++)

            if (x + countSetBits(x) == n)

                return false;

  

        return true;

    }

  

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

    public static void main(String args[])

    {

        if (isBleak(3))

            System.out.println("Yes");

        else

            System.out.println("No");

        if (isBleak(4))

            System.out.println("Yes");

        else

            System.out.println("No");

    }

}

  
/ * Этот код предоставлен Никитой Тивари. * /

python3

# Простая программа на Python 3
# проверить мрачный номер

  
# Функция, чтобы получить не из набора
# бит в двоичном
# представление пройденного
# двоичный номер

def countSetBits(x) :

      

    count = 0

      

    while (x) :

        x = x & (x-1)

        count = count + 1

      

    return count

      
# Возвращает true, если n
# мрачно

def isBleak(n) :

  

    # Проверьте все числа "х"

    # меньше чем n. Если х +

    # countSetBits (x) становится

    # n, тогда n не может быть мрачным.

    for x in range(1, n) :

          

        if (x + countSetBits(x) == n) :

            return False

              

    return True

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

if(isBleak(3)) :

    print( "Yes")

else :

    print("No")

  

if(isBleak(4)) :

    print("Yes")

else

    print( "No")

      
# Этот код предоставлен Никитой Тивари.

C #

// Простая программа на C # для проверки
// Мрачный номер

using System;

  

class GFG {

  

    / * Функция, чтобы получить не из набора

    биты в двоичном представлении

    из переданного двоичного № * /

    static int countSetBits(int x)

    {

        int count = 0;

          

        while (x != 0) {

            x &= (x - 1);

            count++;

        }

          

        return count;

    }

  

    // Возвращает true, если n - Bleak

    static bool isBleak(int n)

    {

          

        // Проверяем все номера

        // 'x' меньше чем n. Если

        // x + countSetBits (x)

        // становится n, тогда n не может

        // быть мрачным

        for (int x = 1; x < n; x++)

          

            if (x + countSetBits(x)

                              == n)

                return false;

  

        return true;

    }

  

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

    public static void Main()

    {

        if (isBleak(3))

            Console.Write("Yes");

        else

            Console.WriteLine("No");

              

        if (isBleak(4))

            Console.Write("Yes");

        else

            Console.Write("No");

    }

}

  
// Этот код предоставлен
// Нитин митталь

PHP

<?php
// Простая PHP-программа
// проверить мрачный номер

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

function countSetBits( $x)

{

    $count = 0;

    while ($x

    {

        $x &= ($x - 1);

        $count++;

    }

    return $count;

}

  
// Возвращает true, если n - Bleak

function isBleak( $n)

{

      

    // Проверяем все числа 'x' меньше

    // чем п. Если x + countSetBits (x)

    // становится n, тогда n не может быть холодным

    for($x = 1; $x < $n; $x++)

        if ($x + countSetBits($x) == $n)

            return false;

  

    return true;

}

  

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

    if(isBleak(3)) 

        echo "Yes\n" ;

    else

        echo "No\n";

          

    if(isBleak(4)) 

        echo "Yes\n" ;

    else

        echo "No\n";

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


Выход :

No
Yes

Временная сложность вышеуказанного решения составляет O (n Log n).

Метод 2 (Эффективный)
Идея основана на том факте, что наибольшее число установленных бит в любом числе, меньшем n, не может превышать потолок Log 2 n. Поэтому нам нужно проверять только числа из диапазона от n — потолокLog2 (n) до n.

bool isBleak(n)
1) Consider all numbers n - ceiling(Log2n) to n-1
    a) If x + countSetBits(x) == n
           return false

2) Return true

Ниже приведена реализация идеи.

C ++

// Эффективная программа на C ++ для проверки Bleak Number
#include <bits/stdc++.h>

using namespace std;

  
/ * Функция, чтобы получить не из установленных битов в двоичном

   представление переданного двоичного кода * /

int countSetBits(int x)

{

    unsigned int count = 0;

    while (x) {

        x &= (x - 1);

        count++;

    }

    return count;

}

  
// Функция для возврата потолка log x
// в базе 2. Например, возвращает 3
// для 8 и 4 для 9.

int ceilLog2(int x)

{

    int count = 0;

    x--;

    while (x > 0) {

        x = x >> 1;

        count++;

    }

    return count;

}

  
// Возвращает true, если n - Bleak

bool isBleak(int n)

{

    // Проверяем все числа 'x' меньше

    // чем п. Если x + countSetBits (x)

    // становится n, тогда n не может быть холодным

    for (int x = n - ceilLog2(n); x < n; x++)

        if (x + countSetBits(x) == n)

            return false;

  

    return true;

}

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

int main()

{

    isBleak(3) ? cout << "Yes\n" : cout << "No\n";

    isBleak(4) ? cout << "Yes\n" : cout << "No\n";

    return 0;

}

Джава

// Эффективная Java-программа для
// проверяем мрачный номер

import java.io.*;

  

class GFG {

  

    / * Функция, чтобы получить нет установленных битов в

    двоичное представление переданного двоичного

    нет. * /

    static int countSetBits(int x)

    {

        int count = 0;

        while (x != 0) {

            x &= (x - 1);

            count++;

        }

        return count;

    }

  

    // Функция для возврата потолка log x

    // в базе 2. Например, возвращает 3

    // для 8 и 4 для 9.

    static int ceilLog2(int x)

    {

        int count = 0;

        x--;

        while (x > 0) {

            x = x >> 1;

            count++;

        }

        return count;

    }

  

    // Возвращает true, если n - Bleak

    static boolean isBleak(int n)

    {

        // Проверяем все числа 'x' меньше

        // чем п. Если x + countSetBits (x)

        // становится n, тогда n не может быть холодным

        for (int x = n - ceilLog2(n); x < n; x++)

            if (x + countSetBits(x) == n)

                return false;

  

        return true;

    }

  

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

    public static void main(String[] args)

    {

        if (isBleak(3))

            System.out.println("Yes");

        else

            System.out.println("No");

  

        if (isBleak(4))

            System.out.println("Yes");

        else

            System.out.println("No");

    }

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

python3

# Эффективная программа на Python 3
# проверить мрачный номер

import math

  
# Функция, чтобы получить не из набора
# бит в двоичном представлении
Количество переданных двоичных файлов

def countSetBits(x) :

      

    count = 0

      

    while (x) :

        x = x & (x - 1

        count = count + 1

      

    return count

      
# Функция возврата потолка
№ log x в базе 2. Для
# пример, он возвращает 3 для 8
№ и 4 на 9.

def ceilLog2(x) :

      

    count = 0

    x = x - 1

      

    while (x > 0) :

        x = x>>1

        count = count + 1

      

    return count

      
# Возвращает true, если n - Bleak

def isBleak(n) :

      

    # Проверьте все числа "х"

    # меньше чем n. Если х +

    # countSetBits (x) становится n,

    # тогда н не может быть мрачным

    for x in range ((n - ceilLog2(n)), n) :

          

        if (x + countSetBits(x) == n) :

            return False

  

    return True

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

if(isBleak(3)) :

    print("Yes"

else :

    print( "No")

      

if(isBleak(4)) :

    print("Yes")

else :

    print("No")

      
# Этот код предоставлен Никитой Тивари.

C #

// Эффективная программа на C # для проверки
// Мрачный номер

using System;

  

class GFG {

  

    / * Функция, чтобы получить не из набора

    биты в двоичном представлении

    из переданного двоичного № * /

    static int countSetBits(int x)

    {

        int count = 0;

        while (x != 0) {

            x &= (x - 1);

            count++;

        }

        return count;

    }

  

    // Функция для возврата потолка

    // из журнала x в базе 2. Для

    // пример, возвращает 3 для 8

    // и 4 для 9.

    static int ceilLog2(int x)

    {

        int count = 0;

        x--;

        while (x > 0) {

            x = x >> 1;

            count++;

        }

        return count;

    }

  

    // Возвращает true, если n - Bleak

    static bool isBleak(int n)

    {

          

        // Проверяем все номера

        // 'x' меньше чем n. Если

        // x + countSetBits (x)

        // становится n, затем n

        // не может быть мрачным

        for (int x = n - ceilLog2(n); 

                          x < n; x++)

            if (x + countSetBits(x) 

                               == n)

                return false;

  

        return true;

    }

  

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

    public static void Main()

    {

        if (isBleak(3))

            Console.WriteLine("Yes");

        else

            Console.WriteLine("No");

  

        if (isBleak(4))

            Console.WriteLine("Yes");

        else

            Console.WriteLine("No");

    }

}

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

PHP

<?php
// Эффективная программа PHP
// проверить мрачный номер

  
/ * Функция, чтобы получить не из набора

   биты в двоичном представлении

   из переданного двоичного № * /

function countSetBits( $x)

{

    $count = 0;

    while ($x)

    {

        $x &= ($x - 1);

        $count++;

    }

    return $count;

}

  
// Функция для возврата потолка log x
// в базе 2. Например, возвращает 3
// для 8 и 4 для 9.

function ceilLog2( $x)

{

      

    $count = 0;

    $x--;

    while ($x > 0) 

    {

        $x = $x >> 1;

        $count++;

    }

    return $count;

}

  
// Возвращает true, если n - Bleak

function isBleak( $n)

{

      

    // Проверяем все числа 'x' меньше

    // чем п. Если x + countSetBits (x)

    // становится n, тогда n не может быть холодным

    for ($x = $n - ceilLog2($n); $x < $n; $x++)

        if ($x + countSetBits($x) == $n)

            return false;

  

    return true;

}

  

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

    if(isBleak(3))

        echo "Yes\n" ;

      

    else

        echo "No\n";

      

    if(isBleak(4))

        echo "Yes\n" ;

      

    else

        echo "No\n";

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


Выход :

No
Yes

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

Примечание. В GCC мы можем напрямую считать установленные биты с помощью __builtin_popcount (). Таким образом, мы можем избежать отдельной функции для подсчета установленных битов.

// C ++ программа для демонстрации __builtin_popcount ()
#include <iostream>

using namespace std;

  

int main()

{

    cout << __builtin_popcount(4) << endl;

    cout << __builtin_popcount(15);

  

    return 0;

}

Выход :

1
4

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

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

Проверьте, является ли номер Bleak

0.00 (0%) 0 votes