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>
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