Dado un número N y cualquier base B . La tarea es verificar si N se puede expresar en la forma a 1 *b 0 + a 2 *b 1 + a 3 *b 2 + ….+ a 101 *b 100 donde cada coeficiente es a 1 , a 2 , a 3 …a 101 son 0, 1 o -1 .
Ejemplos:
Entrada: B = 3, N = 7
Salida: Sí
Explicación:
El número 7 se puede expresar como 1 * 3 0 + (-1) * 3 1 + 1 * 3 2 = 1 – 3 + 9.Entrada: B = 100, N = 50
Salida: No
Explicación:
No hay forma posible de expresar el número.
Enfoque: A continuación se detallan los pasos:
- Si la representación en base B de N consta solo de 0 y 1, entonces la respuesta existe.
- Si la condición anterior no se cumple, itere desde el dígito inferior al superior y si el dígito no es igual a 0 o 1, intente restarle la potencia apropiada de B e incremente el dígito superior.
- Si llega a ser igual a -1 , entonces podemos restar este dígito de potencia, si llega a ser igual a 0, simplemente ignorar, en otros casos, no es posible representar el número en la forma requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if a number
// N can be expressed in base B
bool check(int n, int w)
{
vector<int> a(105);
int p = 0;
// Check if n is greater than 0
while (n > 0) {
a[p++] = n % w;
n /= w;
}
// Initialize a boolean variable
bool flag = true;
for (int i = 0; i <= 100; i++) {
// Check if digit is 0 or 1
if (a[i] == 0 || a[i] == 1)
continue;
// Subtract the appropriate
// power of B from it and
// increment higher digit
else if (a[i] == w
|| a[i] == w - 1)
a[i + 1]++;
else
flag = false;
}
return flag;
}
// Driver Code
int main()
{
// Given Number N and base B
int B = 3, N = 7;
// Function Call
if (check(N, B))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java program for the above approach
class GFG{
// Function to check if a number
// N can be expressed in base B
static boolean check(int n, int w)
{
int[] a = new int[105];
int p = 0;
// Check if n is greater than 0
while (n > 0)
{
a[p++] = n % w;
n /= w;
}
// Initialize a boolean variable
boolean flag = true;
for(int i = 0; i <= 100; i++)
{
// Check if digit is 0 or 1
if (a[i] == 0 || a[i] == 1)
continue;
// Subtract the appropriate
// power of B from it and
// increment higher digit
else if (a[i] == w || a[i] == w - 1)
a[i + 1]++;
else
flag = false;
}
return flag;
}
// Driver Code
public static void main(String[] args)
{
// Given number N and base B
int B = 3, N = 7;
// Function call
if (check(N, B))
System.out.print("Yes");
else
System.out.print("No");
}
}
// This code is contributed by gauravrajput1
Python3
# Python3 program for the above approach
# Function to check if a number
# N can be expressed in base B
def check(n, w):
a = [0 for i in range(105)];
p = 0
# Check if n is greater than 0
while (n > 0):
a[p] = n % w
p += 1
n //= w
# Initialize a boolean variable
flag = True
for i in range(101):
# Check if digit is 0 or 1
if (a[i] == 0 or a[i] == 1):
continue
# Subtract the appropriate
# power of B from it and
# increment higher digit
elif (a[i] == w or a[i] == w - 1):
a[i + 1] += 1
else:
flag = False
return flag
# Driver code
if __name__=="__main__":
# Given number N and base B
B = 3
N = 7
# Function call
if (check(N, B)):
print("Yes")
else:
print("No")
# This code is contributed by rutvik_56
C#
// C# program for the above approach
using System;
class GFG{
// Function to check if a number
// N can be expressed in base B
static bool check(int n, int w)
{
int[] a = new int[105];
int p = 0;
// Check if n is greater than 0
while (n > 0)
{
a[p++] = n % w;
n /= w;
}
// Initialize a bool variable
bool flag = true;
for(int i = 0; i <= 100; i++)
{
// Check if digit is 0 or 1
if (a[i] == 0 || a[i] == 1)
continue;
// Subtract the appropriate
// power of B from it and
// increment higher digit
else if (a[i] == w || a[i] == w - 1)
a[i + 1]++;
else
flag = false;
}
return flag;
}
// Driver Code
public static void Main(String[] args)
{
// Given number N and base B
int B = 3, N = 7;
// Function call
if (check(N, B))
Console.Write("Yes");
else
Console.Write("No");
}
}
// This code is contributed by amal kumar choubey
Javascript
<script>
// javascript program for the above approach
// Function to check if a number
// N can be expressed in base B
function check(n , w) {
var a = Array(105).fill(0);
var p = 0;
// Check if n is greater than 0
while (n > 0) {
a[p++] = n % w;
n /= w;
n = parseInt(n);
}
// Initialize a boolean variable
var flag = true;
for (i = 0; i <= 100; i++) {
// Check if digit is 0 or 1
if (a[i] == 0 || a[i] == 1)
continue;
// Subtract the appropriate
// power of B from it and
// increment higher digit
else if (a[i] == w || a[i] == w - 1)
a[i + 1]++;
else
flag = false;
}
return flag;
}
// Driver Code
// Given number N and base B
var B = 3, N = 7;
// Function call
if (check(N, B))
document.write("Yes");
else
document.write("No");
// This code is contributed by gauravrajput1
</script>
Producción:
Yes
Complejidad temporal: O(log B N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por rohitpal210 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA