Dado un gran número en forma de string N , la tarea es verificar si el número es divisible por 53 o no. Ejemplos:
Entrada: N = 5299947 Salida: Sí Entrada: N = 54 Salida: No
Acercarse:
- Extraiga el último dígito de la string N dada y elimínelo.
- Multiplica ese dígito por 37.
- Reste el producto calculado en el paso anterior del número restante.
- Continúe hasta que reduzcamos la string dada a un número de 3 o cuatro dígitos.
- Convierta la string restante a su forma entera correspondiente y verifique si es divisible por 53 o no.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to check
// whether a number
// is divisible by 53 or not
#include <bits/stdc++.h>
using namespace std;
// Function to check if the
// number is divisible by 53 or not
bool isDivisible(string s)
{
int flag = 0;
while (s.size() > 4) {
int l = s.size() - 1;
int x = (s[l] - '0') * 37;
reverse(s.begin(), s.end());
s.erase(0, 1);
int i = 0, carry = 0;
while (x) {
int d = (s[i] - '0')
- (x % 10)
- carry;
if (d < 0) {
d += 10;
carry = 1;
}
else
carry = 0;
s[i] = (char)(d + '0');
x /= 10;
i++;
}
while (carry && i < l) {
int d = (s[i] - '0') - carry;
if (d < 0) {
d += 10;
carry = 1;
}
else
carry = 0;
s[i] = (char)(d + '0');
i++;
}
reverse(s.begin(), s.end());
}
int num = 0;
for (int i = 0; i < s.size(); i++) {
num = num * 10 + (s[i] - '0');
}
if (num % 53 == 0)
return true;
else
return false;
}
// Driver Code
int main()
{
string N = "18432462191076";
if (isDivisible(N))
cout << "Yes" << endl;
else
cout << "No" << endl;
return 0;
}
Java
// Java program to check whether
// a number is divisible by 53 or not
import java.util.*;
class GFG{
// Function to check if the
// number is divisible by 53 or not
static boolean isDivisible(char []s)
{
while (s.length > 4)
{
int l = s.length - 1;
int x = (s[l] - '0') * 37;
s = reverse(s);
s = Arrays.copyOfRange(s, 1, s.length);
int i = 0, carry = 0;
while (x > 0)
{
int d = (s[i] - '0') -
(x % 10) -
carry;
if (d < 0)
{
d += 10;
carry = 1;
}
else
carry = 0;
s[i] = (char)(d + '0');
x /= 10;
i++;
}
while (carry > 0 && i < l)
{
int d = (s[i] - '0') - carry;
if (d < 0)
{
d += 10;
carry = 1;
}
else
carry = 0;
s[i] = (char)(d + '0');
i++;
}
s = reverse(s);
}
int num = 0;
for(int i = 0; i < s.length; i++)
{
num = num * 10 + (s[i] - '0');
}
if (num % 53 == 0)
return true;
else
return false;
}
static char[] reverse(char []a)
{
int l, r = a.length - 1;
for(l = 0; l < r; l++, r--)
{
char temp = a[l];
a[l] = a[r];
a[r] = temp;
}
return a;
}
// Driver Code
public static void main(String[] args)
{
String N = "18432462191076";
if (isDivisible(N.toCharArray()))
System.out.print("Yes" + "\n");
else
System.out.print("No" + "\n");
}
}
// This code is contributed by Rohit_ranjan
Python3
# Python3 program to check whether a
# number is divisible by 53 or not
# Function to check if the
# number is divisible by 53 or not
def isDivisible(s):
flag = 0
while (len(s) > 4):
l = len(s) - 1
x = (ord(s[l]) - ord('0')) * 37
s = s[::-1]
s = s.replace('0', '', 1)
i = 0
carry = 0
while (x):
d = ((ord(s[i]) - ord('0')) -
(x % 10) - carry)
if (d < 0):
d += 10
carry = 1
else:
carry = 0
s = s.replace(s[i], chr(d + ord('0')), 1)
x //= 10
i += 1
while (carry and i < l):
d = (ord(s[i]) - ord('0')) - carry
if (d < 0):
d += 10
carry = 1
else:
carry = 0
s = s.replace(s[i], chr(d + ord('0')), 1)
i += 1
s = s[::-1]
num = 0
for i in range(len(s)):
num = num * 10 + (ord(s[i]) - ord('0'))
if (num % 53 == 0):
return True
else:
return False
# Driver Code
if __name__ == '__main__':
N = "1843246219106"
if (isDivisible(N)):
print("No")
else:
print("Yes")
# This code is contributed by Surendra_Gangwar
C#
// C# program to check whether
// a number is divisible by 53 or not
using System;
using System.Collections;
using System.Collections.Generic;
class GFG{
// Function to check if the
// number is divisible by 53 or not
static bool isDivisible(char []s)
{
while (s.Length > 4)
{
int l = s.Length - 1;
int x = (s[l] - '0') * 37;
s = reverse(s);
char []tmp = new char[s.Length - 1];
Array.Copy(s, 1, tmp, 0, s.Length - 1);
s = tmp;
int i = 0, carry = 0;
while (x > 0)
{
int d = (s[i] - '0') -
(x % 10) - carry;
if (d < 0)
{
d += 10;
carry = 1;
}
else
carry = 0;
s[i] = (char)(d + '0');
x /= 10;
i++;
}
while (carry > 0 && i < l)
{
int d = (s[i] - '0') - carry;
if (d < 0)
{
d += 10;
carry = 1;
}
else
carry = 0;
s[i] = (char)(d + '0');
i++;
}
s = reverse(s);
}
int num = 0;
for(int i = 0; i < s.Length; i++)
{
num = num * 10 + (s[i] - '0');
}
if (num % 53 == 0)
return true;
else
return false;
}
static char[] reverse(char []a)
{
int l, r = a.Length - 1;
for(l = 0; l < r; l++, r--)
{
char temp = a[l];
a[l] = a[r];
a[r] = temp;
}
return a;
}
// Driver Code
public static void Main(string[] args)
{
string N = "18432462191076";
if (isDivisible(N.ToCharArray()))
Console.Write("Yes" + "\n");
else
Console.Write("No" + "\n");
}
}
// This code is contributed by rutvik_56
Javascript
// JavaScript program to check
// whether a number
// is divisible by 53 or not
// Function to check if the
// number is divisible by 53 or not
function isDivisible(s)
{
s = Array.from(s);
let flag = 0;
while (s.length > 4) {
let l = s.length - 1;
let x = parseInt(s[l]) * 37;
s.reverse();
s.shift();
let i = 0, carry = 0;
while (x > 0) {
let d = (parseInt(s[i]))
- (x % 10)
- carry;
if (d < 0) {
d += 10;
carry = 1;
}
else
carry = 0;
s[i] = d.toString();
x = Math.floor(x / 10);
i++;
}
while ((carry > 0) && i < l) {
let d = parseInt(s[i]) - carry;
if (d < 0) {
d += 10;
carry = 1;
}
else
carry = 0;
s[i] = d.toString();
i++;
}
s.reverse();
}
let num = parseInt((s).join(""));
if (num % 53 == 0)
return true;
else
return false;
}
// Driver Code
let N = "18432462191076";
if (isDivisible(N))
console.log("Yes");
else
console.log("No");
// This code is contributed by phasing17
Producción:
Yes
Complejidad de tiempo: O(n), donde n es el tamaño de la string dada N
Espacio auxiliar: O(1), ya que no se requiere espacio adicional