Cuente números de un rango dado que tengan el mismo primer y último dígito en su representación binaria

Dados dos números enteros L y R , la tarea es encontrar el conteo de números en el rango [L, R] cuyo primer y último dígito en la representación binaria son iguales.

Ejemplos:

Entrada: L = 1, R = 5
Salida: 3
Explicación:
(1) ₁₀ = (1) ₂
(2) ₁₀ = (10) ₂
(3) ₁₀ = (11) ₂
(4) ₁₀ = (100) ₂
(5) ₁₀ = (101) ₂
Por lo tanto, 1, 3, 5 tienen el mismo primer y último dígito en su representación binaria.

Entrada: L = 6, R = 30
Salida: 12

Enfoque ingenuo: el enfoque más simple es iterar sobre el rango L a R y encontrar la representación binaria de todos los números y verificar para cada uno de ellos, si el primer y el último dígito en su representación binaria es el mismo o no. 
Complejidad de tiempo: O((RL)log(RL))
Espacio auxiliar: O(1)

Enfoque eficiente: el problema dado se puede resolver con base en las siguientes observaciones:

• Los números impares siempre terminan en 1 en su representación binaria.
• Cada número tiene el bit inicial como 1 en su representación binaria.
• Por lo tanto, el problema se reduce a encontrar el conteo de números impares en el rango dado.

Siga los pasos a continuación para resolver el problema:

• Encuentre el conteo de números impares en el rango [1, R] y guárdelo en una variable, digamos X .
• De manera similar, encuentre el conteo de números impares en el rango [1, L – 1] . Que sea Y.
• Escriba X – Y como respuesta.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count numbers in range
// [L, R] having same first and last
// digit in the binary representation
void Count_numbers(int L, int R)
{
    int count = (R - L) / 2;
 
    if (R % 2 != 0 || L % 2 != 0)
        count += 1;
 
    cout << count << endl;
}
 
// Drivers code
int main()
{
 
    // Given range [L, R]
    int L = 6, R = 30;
 
    // Function Call
    Count_numbers(L, R);
}

// Java program to implement
// the above approach
import java.util.*;
class GFG
{
        
// Function to count numbers in range
// [L, R] having same first and last
// digit in the binary representation
static void Count_numbers(int L, int R)
{
    int count = (R - L) / 2;
    if (R % 2 != 0 || L % 2 != 0)
        count += 1;
    System.out.print(count);
}
    
// Driver code
public static void main(String[] args)
{
    // Given range [L, R]
    int L = 6, R = 30;
 
    // Function Call
    Count_numbers(L, R);
}
}
 
// This code is contributed by sanjoy_62

# Python program for the above approach
 
# Function to count numbers in range
# [L, R] having same first and last
# digit in the binary representation
def Count_numbers(L, R) :  
    count = (R - L) // 2
    if (R % 2 != 0 or L % 2 != 0) :
        count += 1
    print(count)
 
# Drivers code
 
# Given range [L, R]
L = 6
R = 30
 
# Function Call
Count_numbers(L, R)
 
# This code is contributed by code_hunt.

// C# program to implement
// the above approach
using System;
class GFG
{
        
// Function to count numbers in range
// [L, R] having same first and last
// digit in the binary representation
static void Count_numbers(int L, int R)
{
    int count = (R - L) / 2;
    if (R % 2 != 0 || L % 2 != 0)
        count += 1;
    Console.Write(count);
}
    
// Driver code
public static void Main(String[] args)
{
   
    // Given range [L, R]
    int L = 6, R = 30;
 
    // Function Call
    Count_numbers(L, R);
}
}
 
// This code is contributed by 29AjayKumar

<script>
// javascript program to implement
// the above approach
 
    // Function to count numbers in range
    // [L, R] having same first and last
    // digit in the binary representation
    function Count_numbers(L , R)
    {
        var count = (R - L) / 2;
        if (R % 2 != 0 || L % 2 != 0)
            count += 1;
        document.write(count);
    }
 
    // Driver code
     
        // Given range [L, R]
        var L = 6, R = 30;
 
        // Function Call
        Count_numbers(L, R);
 
// This code is contributed by Rajput-Ji
</script>

12

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)