Dado un número grande como una string, encuentre el resto del número cuando se divide por 7.
Ejemplos:
Input : num = 1234 Output : 2 Input : num = 1232 Output : 0 Input : num = 12345 Output : 4
El enfoque simple es convertir una string en un número y realizar la operación de modificación. Pero este enfoque no funcionará para strings largas.
Existe un enfoque que también funciona para grandes números.
A continuación se muestran los pasos. Sea el número dado «num»
- Usamos una serie 1, 3, 2, -1, -3, -2 para encontrar el resto (la intuición detrás de la serie se analiza a continuación).
- Inicializar el resultado como 0.
- Traverse num desde el final y por encima de la serie desde el principio. Para cada dígito recorrido, multiplíquelo con el siguiente dígito de la serie y agregue la multiplicación al resultado.
- Siga repitiendo el paso 3 mientras haya más dígitos para procesar. Si hay más de 6 (número de términos en la serie) dígitos, comience a recorrer la serie desde el principio.
- Después de cada paso, seguimos haciendo resultado = resultado % 7 para asegurarnos de que el resultado siga siendo inferior a 7.
Ilustración :
let us take above Example where number is 12345.
We reverse the number from end and series from
the beginning and keep adding multiplication to
the result.
(12345 % 7) = (5*1 + 4*3 + 3*2 + 2*(-1) + 1*(-3)) % 7
= (5 + 12 + 6 - 2 - 3)%7
= (18) % 7
= 4
hence 4 will be the remainder when we divide
the number 12345 by 7.
¿Cómo funciona esta fórmula de serie?
A continuación se muestra la intuición detrás de la serie.
1 % 7 = 1 10 % 7 = 3 100 % 7 = 2 1000 % 7 = 6 = (-1) % 7 10000 % 7 = 4 = (-3) % 7 100000 % 7 = 5 = (-2) % 7 The series repeats itself for larger powers 1000000 % 7 = 1 10000000 % 7 = 3 .............. ............... The above property of modular division with 7 and associative properties of modular arithmetic are the basis of the approach used here.
Implementación:
C++
// C++ program to find remainder of a large
// number when divided by 7.
#include<iostream>
using namespace std;
/* Function which returns Remainder after dividing
the number by 7 */
int remainderWith7(string num)
{
// This series is used to find remainder with 7
int series[] = {1, 3, 2, -1, -3, -2};
// Index of next element in series
int series_index = 0;
int result = 0; // Initialize result
// Traverse num from end
for (int i=num.size()-1; i>=0; i--)
{
/* Find current digit of nun */
int digit = num[i] - '0';
// Add next term to result
result += digit * series[series_index];
// Move to next term in series
series_index = (series_index + 1) % 6;
// Make sure that result never goes beyond 7.
result %= 7;
}
// Make sure that remainder is positive
if (result < 0)
result = (result + 7) % 7;
return result;
}
/* Driver program */
int main()
{
string str = "12345";
cout << "Remainder with 7 is "
<< remainderWith7(str);
return 0;
}
Java
// Java program to find remainder of a large
// number when divided by 7.
class GFG
{
// Function which return Remainder
// after dividingthe number by 7
static int remainderWith7(String num)
{
// This series is used to
// find remainder with 7
int series[] = {1, 3, 2, -1, -3, -2};
// Index of next element in series
int series_index = 0;
// Initialize result
int result = 0;
// Traverse num from end
for (int i = num.length() - 1; i >= 0; i--)
{
/* Find current digit of nun */
int digit = num.charAt(i) - '0';
// Add next term to result
result += digit * series[series_index];
// Move to next term in series
series_index = (series_index + 1) % 6;
// Make sure that result never goes beyond 7.
result %= 7;
}
// Make sure that remainder is positive
if (result < 0)
result = (result + 7) % 7;
return result;
}
// Driver code
public static void main (String[] args)
{
String str = "12345";
System.out.print("Remainder with 7 is "
+remainderWith7(str));
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python3 program to find remainder of
# a large number when divided by 7.
# Function which return Remainder
# after dividing the number by 7
def remainderWith7(num):
# This series is used to
# find remainder with 7
series = [1, 3, 2, -1, -3, -2];
# Index of next element
# in series
series_index = 0;
# Initialize result
result = 0;
# Traverse num from end
for i in range((len(num) - 1), -1, -1):
# Find current digit of num
digit = ord(num[i]) - 48;
# Add next term to result
result += digit * series[series_index];
# Move to next term in series
series_index = (series_index + 1) % 6;
# Make sure that result
# never goes beyond 7.
result %= 7;
# Make sure that remainder
# is positive
if (result < 0):
result = (result + 7) % 7;
return result;
# Driver Code
str = "12345";
print("Remainder with 7 is",
remainderWith7(str));
# This code is contributed by mits
C#
// C# program to find the remainder of
// a large number when divided by 7.
using System;
class GFG
{
// Function which return Remainder
// after dividingthe number by 7
static int remainderWith7(String num)
{
// This series is used to
// find remainder with 7
int []series = {1, 3, 2, -1, -3, -2};
// Index of next element in series
int series_index = 0;
// Initialize result
int result = 0;
// Traverse num from end
for (int i = num.Length - 1; i >= 0; i--)
{
/* Find current digit of nun */
int digit = num[i] - '0';
// Add next term to result
result += digit * series[series_index];
// Move to next term in series
series_index = (series_index + 1) % 6;
// Make sure that result never goes beyond 7.
result %= 7;
}
// Make sure that remainder is positive
if (result < 0)
result = (result + 7) % 7;
return result;
}
// Driver code
public static void Main ()
{
String str = "12345";
Console.Write("Remainder with 7 is " +
remainderWith7(str));
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP program to find remainder of
// a large number when divided by 7.
/* Function which return Remainder
after dividing the number by 7 */
function remainderWith7($num)
{
// This series is used to
// find remainder with 7
$series = array(1, 3, 2, -1, -3, -2);
// Index of next element
// in series
$series_index = 0;
// Initialize result
$result = 0;
// Traverse num from end
for($i = strlen($num) - 1; $i >= 0; $i--)
{
// Find current digit of num
$digit = $num[$i] - '0';
// Add next term to result
$result += $digit *
$series[$series_index];
// Move to next term in series
$series_index = ($series_index + 1) % 6;
// Make sure that result
// never goes beyond 7.
$result %= 7;
}
// Make sure that remainder
// is positive
if ($result < 0)
$result = ($result + 7) % 7;
return $result;
}
// Driver Code
{
$str = "12345";
echo "Remainder with 7 is ",
(remainderWith7($str));
return 0;
}
// This code is contributed by nitin mittal.
?>
Javascript
<script>
// Javascript program to find remainder of a large
// number when divided by 7.
/* Function which returns Remainder after dividing
the number by 7 */
function remainderWith7(num)
{
// This series is used to find remainder with 7
series = [1, 3, 2, -1, -3, -2]
// Index of next element in series
var series_index = 0;
var result = 0; // Initialize result
// Traverse num from end
for (var i = num.length - 1; i >= 0; i--)
{
/* Find current digit of nun */
var digit = num[i] - '0';
// Add next term to result
result += digit * series[series_index];
// Move to next term in series
series_index = (series_index + 1) % 6;
// Make sure that result never goes beyond 7.
result %= 7;
}
// Make sure that remainder is positive
if (result < 0)
result = (result + 7) % 7;
return result;
}
/* Driver program */
var str = "12345";
document.write("Remainder with 7 is " + remainderWith7(str));
// This code is contributed by oob2000.
</script>
Producción
Remainder with 7 is 4
Complejidad temporal : O(n)
Espacio auxiliar : O(1)
Este artículo es una contribución de Kuldeep Singh . 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.
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