Dado un número decimal N, la tarea es verificar si un número tiene ceros consecutivos o no después de convertir el número a su notación basada en K.
Ejemplos:
Entrada: N = 4, K = 2
Salida: No
4 en base 2 es 100, como hay 2 consecutivos, la respuesta es No.Entrada: N = 15, K = 8
Salida: Sí
15 en base 8 es 17, Como no hay 0 consecutivos, la respuesta es Sí.
Enfoque : primero convierta el número N en base K y luego simplemente verifique si el número tiene ceros consecutivos o no.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include<bits/stdc++.h>
using namespace std;
// Function to convert N into base K
int toK(int N, int K)
{
// Weight of each digit
int w = 1;
int s = 0;
while (N != 0)
{
int r = N % K;
N = N/K;
s = r * w + s;
w *= 10;
}
return s;
}
// Function to check for consecutive 0
bool check(int N)
{
// Flag to check if there are consecutive
// zero or not
bool fl = false;
while (N != 0)
{
int r = N % 10;
N = N/10;
// If there are two consecutive zero
// then returning False
if (fl == true and r == 0)
return false;
if (r > 0)
{
fl = false;
continue;
}
fl = true;
}
return true;
}
// We first convert to given base, then
// check if the converted number has two
// consecutive 0s or not
void hasConsecutiveZeroes(int N, int K)
{
int z = toK(N, K);
if (check(z))
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
// Driver code
int main()
{
int N = 15;
int K = 8;
hasConsecutiveZeroes(N, K);
}
// This code is contributed by
// Surendra_Gangwar
Java
// Java implementation of the above approach
import java.util.*;
class GFG
{
// Function to convert N into base K
static int toK(int N, int K)
{
// Weight of each digit
int w = 1;
int s = 0;
while (N != 0)
{
int r = N % K;
N = N / K;
s = r * w + s;
w *= 10;
}
return s;
}
// Function to check for consecutive 0
static boolean check(int N)
{
// Flag to check if there are consecutive
// zero or not
boolean fl = false;
while (N != 0)
{
int r = N % 10;
N = N / 10;
// If there are two consecutive zero
// then returning False
if (fl == true && r == 0)
return false;
if (r > 0)
{
fl = false;
continue;
}
fl = true;
}
return true;
}
// We first convert to given base, then
// check if the converted number has two
// consecutive 0s or not
static void hasConsecutiveZeroes(int N, int K)
{
int z = toK(N, K);
if (check(z))
System.out.println("Yes");
else
System.out.println("No");
}
// Driver code
public static void main(String[] args)
{
int N = 15;
int K = 8;
hasConsecutiveZeroes(N, K);
}
}
// This code is contributed by Princi Singh
Python3
# Python implementation of the above approach
# We first convert to given base, then
# check if the converted number has two
# consecutive 0s or not
def hasConsecutiveZeroes(N, K):
z = toK(N, K)
if (check(z)):
print("Yes")
else:
print("No")
# Function to convert N into base K
def toK(N, K):
# Weight of each digit
w = 1
s = 0
while (N != 0):
r = N % K
N = N//K
s = r * w + s
w* = 10
return s
# Function to check for consecutive 0
def check(N):
# Flag to check if there are consecutive
# zero or not
fl = False
while (N != 0):
r = N % 10
N = N//10
# If there are two consecutive zero
# then returning False
if (fl == True and r == 0):
return False
if (r > 0):
fl = False
continue
fl = True
return True
# Driver code
N, K = 15, 8
hasConsecutiveZeroes(N, K)
C#
// C# implementation of the above approach
using System;
class GFG
{
// Function to convert N into base K
static int toK(int N, int K)
{
// Weight of each digit
int w = 1;
int s = 0;
while (N != 0)
{
int r = N % K;
N = N / K;
s = r * w + s;
w *= 10;
}
return s;
}
// Function to check for consecutive 0
static Boolean check(int N)
{
// Flag to check if there are consecutive
// zero or not
Boolean fl = false;
while (N != 0)
{
int r = N % 10;
N = N / 10;
// If there are two consecutive zero
// then returning False
if (fl == true && r == 0)
return false;
if (r > 0)
{
fl = false;
continue;
}
fl = true;
}
return true;
}
// We first convert to given base, then
// check if the converted number has two
// consecutive 0s or not
static void hasConsecutiveZeroes(int N, int K)
{
int z = toK(N, K);
if (check(z))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
// Driver code
public static void Main(String[] args)
{
int N = 15;
int K = 8;
hasConsecutiveZeroes(N, K);
}
}
// This code is contributed by 29AjayKumar
PHP
<?php
// PHP implementation of the above approach
// We first convert to given base,
// then check if the converted number
// has two consecutive 0s or not
function hasConsecutiveZeroes($N, $K)
{
$z = toK($N, $K);
if (check($z))
print("Yes");
else
print("No");
}
// Function to convert N into base K
function toK($N, $K)
{
// Weight of each digit
$w = 1;
$s = 0;
while ($N != 0)
{
$r = $N % $K;
$N = (int)($N / $K);
$s = $r * $w + $s;
$w *= 10;
}
return $s;
}
// Function to check for consecutive 0
function check($N)
{
// Flag to check if there are
// consecutive zero or not
$fl = false;
while ($N != 0)
{
$r = $N % 10;
$N = (int)($N / 10);
// If there are two consecutive
// zero then returning false
if ($fl == true and $r == 0)
return false;
if ($r > 0)
{
$fl = false;
continue;
}
$fl = true;
}
return true;
}
// Driver code
$N = 15;
$K = 8;
hasConsecutiveZeroes($N, $K);
// This code is contributed by mits
?>
Javascript
<script>
// Javascript implementation of the above approach
// Function to convert N into base K
function toK(N, K)
{
// Weight of each digit
let w = 1;
let s = 0;
while (N != 0)
{
let r = N % K;
N = parseInt(N / K);
s = r * w + s;
w *= 10;
}
return s;
}
// Function to check for consecutive 0
function check(N)
{
// Flag to check if there are consecutive
// zero or not
let fl = false;
while (N != 0)
{
let r = N % 10;
N = parseInt(N/10);
// If there are two consecutive zero
// then returning False
if (fl == true && r == 0)
return false;
if (r > 0)
{
fl = false;
continue;
}
fl = true;
}
return true;
}
// We first convert to given base, then
// check if the converted number has two
// consecutive 0s or not
function hasConsecutiveZeroes(N, K)
{
let z = toK(N, K);
if (check(z))
document.write("Yes");
else
document.write("No");
}
// Driver code
let N = 15;
let K = 8;
hasConsecutiveZeroes(N, K);
// This code is contributed by souravmahato348
</script>
Producción:
Yes
Complejidad temporal: O(log k n + log 10 n), donde n y k representan el valor de los números enteros dados.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.