Программа для поиска N-го натурального числа с ровно двумя установленными битами

Опубликовано: 4 Декабря, 2021

Учитывая целое число N , задача состоит в том, чтобы найти N-е натуральное число с ровно двумя установленными битами.
Примеры:

Input: N = 4
Output: 9
Explanation:
Numbers with exactly two bits set: 3, 5, 6, 9, 10, 12, …
4th number in this is 9
Input: N = 15
Output: 48

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Наивный подход:

Выполните цикл по всем натуральным числам и для каждого числа проверьте, установлены ли в нем два бита или нет, подсчитав заданные биты в числе.
Выведите N-е число с двумя заданными битами.

Эффективный подход:

Найдите крайний левый установленный бит, найдя раздел, которому принадлежит N (в разделе «i» есть номера «i»).
Чтобы найти другой установленный бит, нам нужно сначала найти расстояние N от последнего числа предыдущего раздела. Исходя из их разницы, мы устанавливаем соответствующий бит.

Примечание. Чтобы установить i-й бит (i = 0, 1, 2…) в число K:

 k = k | (1 << (i))

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

C ++

 // C++ Code to find the Nth number
 // with exactly two bits set
 #include <bits/stdc++.h>
 using namespace std;
 // Function to find the Nth number
 // with exactly two bits set
 void findNthNum( long long int N)
 {
    long long int bit_L = 1, last_num = 0; 
    // Keep incrementing until
    // we reach the partition of 'N'
    // stored in bit_L
    while (bit_L * (bit_L + 1) / 2 < N) {
        last_num = last_num + bit_L;
        bit_L++;
    }
    // set the rightmost bit
    // based on bit_R
    int bit_R = N - last_num - 1; 
    cout << (1 << bit_L) + (1 << bit_R)
         << endl;
 }
 // Driver code
 int main()
 {
    long long int N = 13; 
    findNthNum(N);
    return 0;
 }

Джава

 // Java Code to find the Nth number
 // with exactly two bits set
 class GFG{
 
// Function to find the Nth number
 // with exactly two bits set
 static void findNthNum( int N)
 {
 
    int bit_L = 1 , last_num = 0 ;
 
    // Keep incrementing until
    // we reach the partition of 'N'
    // stored in bit_L
    while (bit_L * (bit_L + 1 ) / 2 < N) {
        last_num = last_num + bit_L;
        bit_L++;
    }
 
    // set the rightmost bit
    // based on bit_R
    int bit_R = N - last_num - 1 ;
 
    System.out.print(( 1 << bit_L) + ( 1 << bit_R)
         + "
" );
 }
 
// Driver code
 public static void main(String[] args)
 {
    int N = 13 ;
 
    findNthNum(N);
 }
 }
 // This code is contributed by Princi Singh

Python3

 # Python Code to find the Nth number
 # with exactly two bits set
 # Function to find the Nth number
 # with exactly two bits set
 def findNthNum(N): 
    bit_L = 1 ;
    last_num = 0 ; 
    # Keep incrementing until
    # we reach the partition of 'N'
    # stored in bit_L
    while (bit_L * (bit_L + 1 ) / 2 < N):
        last_num = last_num + bit_L;
        bit_L + = 1 ;
    
    # set the rightmost bit
    # based on bit_R
    bit_R = N - last_num - 1 ; 
    print (( 1 << bit_L) + ( 1 << bit_R)); 
 # Driver code
 if __name__ = = '__main__' :
    N = 13 ; 
    findNthNum(N);
 # This code contributed by PrinciRaj1992

C #

 // C# Code to find the Nth number
 // with exactly two bits set
 using System;
 class GFG{
  
// Function to find the Nth number
 // with exactly two bits set
 static void findNthNum( int N)
 {
  
    int bit_L = 1, last_num = 0;
  
    // Keep incrementing until
    // we reach the partition of 'N'
    // stored in bit_L
    while (bit_L * (bit_L + 1) / 2 < N) {
        last_num = last_num + bit_L;
        bit_L++;
    }
  
    // set the rightmost bit
    // based on bit_R
    int bit_R = N - last_num - 1;
  
    Console.Write((1 << bit_L) + (1 << bit_R)
         + "
" );
 }
  
// Driver code
 public static void Main(String[] args)
 {
    int N = 13;
  
    findNthNum(N);
 }
 }
 // This code is contributed by Princi Singh

Javascript

 <script>
 // JavaScript Code to find the Nth number
 // with exactly two bits set
 // Function to find the Nth number
 // with exactly two bits set
 function findNthNum(N)
 {
    let bit_L = 1, last_num = 0;
    // Keep incrementing until
    // we reach the partition of 'N'
    // stored in bit_L
    while (bit_L * (bit_L + 1) / 2 < N) {
        last_num = last_num + bit_L;
        bit_L++;
    }
    // set the rightmost bit
    // based on bit_R
    let bit_R = N - last_num - 1;
    document.write((1 << bit_L) + (1 << bit_R)
        + "<br>" );
 }
 // Driver code
 let N = 13;
 findNthNum(N);
 // This code is contributed by Mayank Tyagi
 </script>

Выход:

Сложность времени: O (разделение числа)

Внимание компьютерщик! Укрепите свои основы с помощью базового курса программирования Python и изучите основы.

Для начала подготовьтесь к собеседованию. Расширьте свои концепции структур данных с помощью курса Python DS. А чтобы начать свое путешествие по машинному обучению, присоединяйтесь к курсу Машинное обучение - базовый уровень.

Python C++ Placements

Программа для поиска N-го натурального числа с ровно двумя установленными битами

C ++

Джава

Python3

C #

Javascript

РЕКОМЕНДУЕМЫЕ СТАТЬИ