Comprueba si un número N comienza con 1 en base b

Posted on by Rudeus Greyrat

Dado un número N y base b, si N en base b, la representación comienza con 1, imprime Sí, de lo contrario, imprime No 

Ejemplos:  

Input : n = 6, b = 4
Output : Yes
6 can be written as 12_4 in base 4so answer is Yes as it starts with 1Input : n = 24, b = 2Output : Yes24 can be written as 11000_2 in base 2so answer is Yes as it starts with 1Input :  n = 24, b = 7Output : No24 can be written as 33_7 in base 7so answer is No as it starts with 3

Cuando un número N se representa en la base ‘b’, se convierte en una secuencia de longitud m+1  b_{m} [Tex]b_{m-1} [/Tex]….. b_0 lo que implica  b_{m} * b^{m} +  b_{m-1} * b^{m-1} …..+ b_0 * b^0 = N 

El número más pequeño en la base b y que comienza con ‘1’, es decir, 100..00 y m+1 dígitos en la base es  b^{m}
y el número más grande es 2* b^{m} -1. Entonces, N debe estar en este rango. 
b^{m} <= N <= 2* b^{m} -1 
Ahora, otra cosa a tener en cuenta es que m no puede exceder el piso ( log_2 (N)) porque cuando representamos cualquier número en base 2, se convierte en una secuencia de solo 1 y 0, por lo que la longitud de esta secuencia siempre será mayor que cualquier otra representación base y su longitud será igual a piso( log_2 (N))+1. 

Entonces, para verificar una base ‘b’ dada, si N comienza con 1 o no, atravesaremos de m = 1 a m = piso (( log_2 N)) y verificaremos si para cualquier m N se encuentra en el rango  b^{m} <= N <= 2 * b^{m} -1 o no y, en consecuencia, imprima «Sí» o «No». 
 

C++

// C++ program to check if number starts with
// one in base b representation
#include <bits/stdc++.h>
using namespace std;
 
// Returns true if n starts with  1 in
// base b representation
bool CheckIfstartsWithOne(int n, int b)
{
    // highest m can be log2(n)
    int m = log2(n);
    for (int i = 1; i <= m; i++) {
        // if b^m <= N <= 2*b^m - 1,
        // return true
        if (n >= pow(b, i) && n <= 2 * pow(b, i) - 1)
            return true;
    }
    return false;
}
 
// printing yes or no
void printYesORno(int n, int b)
{
    if (CheckIfstartsWithOne(n, b) == true)
        cout << "Yes" << endl;
    else if (CheckIfstartsWithOne(n, b) == false)
        cout << "No" << endl;
}
 
// driver function
int main()
{
    printYesORno(6, 4);
    printYesORno(24, 2);
    printYesORno(24, 7);
    printYesORno(24, 15);
}

Java

// Java program to check if number starts with
// one in base b representation
 
class GFG {
     
    // Returns true if n starts with 1 in
    // base b representation
    static boolean CheckIfstartsWithOne(int n, int b)
    {
         
        // highest m can be log2(n)
        int m = (int)(Math.log10(n) / Math.log10(2));
        for (int i = 1; i <= m; i++) {
             
            // if b^m <= N <= 2*b^m - 1,
            // return true
            if (n >= (int)Math.pow(b, i) &&
                n <= 2 * (int)Math.pow(b, i) - 1)
                return true;
        }
         
        return false;
    }
 
    // Driver method
    public static void main(String args[])
    {
        System.out.println(
           CheckIfstartsWithOne(6, 4) ? "Yes" : "No");
            
        System.out.println(
           CheckIfstartsWithOne(24, 2) ? "Yes" : "No");
            
        System.out.println(
           CheckIfstartsWithOne(24, 7) ? "Yes" : "No");
            
        System.out.println(
           CheckIfstartsWithOne(24, 15) ? "Yes" : "No");
    }
}

Python3

# Python3 program to check
# if number starts with one
# in base b representation
import math
 
# Returns true if n
# starts with 1 in
# base b representation
def CheckIfstartsWithOne(n, b):
     
    # highest m can be log2(n)
    m = (int)(math.log2(n));
    for i in range (1, m + 1):
         
        # if b^m <= N <= 2*b^m - 1,
        #return true
        x = (int)(math.pow(b, i));
        if n >= x and n <= 2 * x - 1:
            return 1;
    return 0;
 
# printing yes or no
def printYesORno(n, b):
    if CheckIfstartsWithOne(n, b) == 1:
        print("Yes");
    if CheckIfstartsWithOne(n, b) == 0:
        print("No");
         
# Driver Code
printYesORno(6, 4);
printYesORno(24, 2);
printYesORno(24, 7);
printYesORno(24, 15);
 
# This code is contributed by mits.

C#

// C# program to check if number starts with
// one in base b representation
using System;
 
class GFG{
     
// Returns true if n starts with 1 in
// base b representation
static bool CheckIfstartsWithOne(int n, int b)
{
     
    // highest m can be log2(n)
    int m = (int)(Math.Log10(n) / Math.Log10(2));
    for(int i = 1; i <= m; i++)
    {
         
        // if b^m <= N <= 2*b^m - 1,
        // return true
        if (n >= (int)Math.Pow(b, i) &&
            n <= 2 * (int)Math.Pow(b, i) - 1)
            return true;
    }
     
    return false;
}
 
// Driver code
public static void Main(String []args)
{
    Console.WriteLine(
       CheckIfstartsWithOne(6, 4) ? "Yes" : "No");
        
    Console.WriteLine(
       CheckIfstartsWithOne(24, 2) ? "Yes" : "No");
        
    Console.WriteLine(
       CheckIfstartsWithOne(24, 7) ? "Yes" : "No");
        
    Console.WriteLine(
       CheckIfstartsWithOne(24, 15) ? "Yes" : "No");
}
}
 
// This code is contributed by Princi Singh

PHP

<?php
// PHP program to check if
// number starts with one
// in base b representation
 
// Returns true if n starts
// with 1 in base b representation
function CheckIfstartsWithOne($n, $b)
{
    // highest m can be log2(n)
    $m = log($n, 2);
    for ($i = 1; $i <= $m; $i++)
    {
        // if b^m <= N <= 2*b^m - 1,
        // return true
        if ($n >= pow($b, $i) &&
                $n <= 2 * pow($b, $i) - 1)
            return true;
    }
    return false;
}
 
// printing yes or no
function printYesORno($n, $b)
{
    if (CheckIfstartsWithOne($n, $b) == true)
        echo "Yes" ,"\n";
    else if (CheckIfstartsWithOne($n, $b) == false)
        echo "No" ,"\n";
}
 
// Driver Code
printYesORno(6, 4);
printYesORno(24, 2);
printYesORno(24, 7);
printYesORno(24, 15);
 
// This code is contributed by ajit
?>

Javascript

<script>
    // Javascript program to check if number starts
    // with one in base b representation
     
    // Returns true if n starts with
    // 1 in base b representation
    function CheckIfstartsWithOne(n, b)
    {
           
        // highest m can be log2(n)
        let m = parseInt(Math.log10(n) / Math.log10(2), 10);
           
        for (let i = 1; i <= m; i++)
        {
               
            // if b^m <= N <= 2*b^m - 1,
            // return true
            if (n >= Math.pow(b, i) && n <= 2 * Math.pow(b, i) - 1)
                return true;
        }
           
        return false;
    }
     
    document.write(CheckIfstartsWithOne(6, 4) ? "Yes" + "</br>" : "No" + "</br>");
              
    document.write(CheckIfstartsWithOne(24, 2) ? "Yes" + "</br>" : "No" + "</br>");
 
    document.write(CheckIfstartsWithOne(24, 7) ? "Yes" + "</br>" : "No" + "</br>");
 
    document.write(CheckIfstartsWithOne(24, 15) ? "Yes" : "No");
     
</script>

Producción : 

Yes
Yes
No
Yes

Complejidad de tiempo: O(m), donde m se calcula como log2(n)
Espacio auxiliar: O(1), ya que no se requiere espacio adicional
Este artículo es una contribución de Ayush Jha . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *