Given a number N, the task is to find the remainder when N is divided by R (a two-digit Number). The input of the Number may be very large.
Examples:
Input: N = 13589234356546756, R = 13 Output: 11 Input: N = 3435346456547566345436457867978, R = 17 Output: 13
- Get the digit of N one by one from left to right.
- For each digit, combine with next digit if its less than R.
- If the combination at any point reaches above R, take and store the Remainder.
- Repeat the above steps for all digits from left to right.
Below is the program that implements the above approach:
C
// C implementation to find Remainder// when a large Number is divided by R#include <stdio.h>#include <string.h>// Function to Return Remainderint Remainder(char str[], int R){ // len is variable to store the // length of Number string. int len = strlen(str); int Num, Rem = 0; // loop that find Remainder for (int i = 0; i < len; i++) { Num = Rem * 10 + (str[i] - '0'); Rem = Num % R; } // Return the remainder return Rem;}// Driver codeint main(){ // Get the large number as string char str[] = "13589234356546756"; // Get the divisor R int R = 13; // Find and print the remainder printf("%d",Remainder(str, R)); return 0;}// This code is contributed by kothavvsaakash. |
C++
// CPP implementation to find Remainder// when a large Number is divided by R#include <bits/stdc++.h>using namespace std;// Function to Return Remainderint Remainder(string str, int R){ // len is variable to store the // length of Number string. int len = str.length(); int Num, Rem = 0; // loop that find Remainder for (int i = 0; i < len; i++) { Num = Rem * 10 + (str[i] - '0'); Rem = Num % R; } // Return the remainder return Rem;}// Driver codeint main(){ // Get the large number as string string str = "13589234356546756"; // Get the divisor R int R = 13; // Find and print the remainder cout << Remainder(str, R); return 0;} |
Java
// Java implementation to find Remainder// when a large Number is divided by Rclass GFG{ // Function to Return Remainder static int Remainder(String str, int R) { // len is variable to store the // length of Number string. int len = str.length(); int Num, Rem = 0; // loop that find Remainder for (int i = 0; i < len; i++) { Num = Rem * 10 + (str.charAt(i) - '0'); Rem = Num % R; } // Return the remainder return Rem; } // Driver code public static void main( String [] args) { // Get the large number as string String str = "13589234356546756"; // Get the divisor R int R = 13; // Find and print the remainder System.out.println(Remainder(str, R)); }}// This code is contributed// by ihritik |
Python 3
# Python 3 implementation to # find Remainder when a large# Number is divided by R# Function to Return Remainderdef Remainder(str, R): # len is variable to store the # length of Number string. l = len(str) Rem = 0 # loop that find Remainder for i in range(l): Num = Rem * 10 + (ord(str[i]) - ord('0')) Rem = Num % R # Return the remainder return Rem# Driver codeif __name__ == "__main__": # Get the large number # as string str = "13589234356546756" # Get the divisor R R = 13 # Find and print the remainder print(Remainder(str, R))# This code is contributed # by ChitraNayal |
Javascript
<script>// Javascript implementation to find Remainder// when a large Number is divided by R// Function to Return Remainderfunction Remainder(str, R){ // len is variable to store the // length of Number string. var len = str.length; var Num, Rem = 0; // loop that find Remainder for (var i = 0; i < len; i++) { Num = Rem * 10 + (str[i] - '0'); Rem = Num % R; } // Return the remainder return Rem;}// Driver code// Get the large number as stringvar str = "13589234356546756";// Get the divisor Rvar R = 13;// Find and print the remainderdocument.write(Remainder(str, R));// This code is contributed by noob2000.</script> |
C#
// C# implementation to find // Remainder when a large// Number is divided by Rusing System;class GFG{ // Function to Return Remainderstatic int Remainder(String str, int R){ // len is variable to store the // length of Number string. int len = str.Length; int Num, Rem = 0; // loop that find Remainder for (int i = 0; i < len; i++) { Num = Rem * 10 + (str[i] - '0'); Rem = Num % R; } // Return the remainder return Rem;}// Driver codepublic static void Main(){ // Get the large number as string String str = "13589234356546756"; // Get the divisor R int R = 13; // Find and print the remainder Console.WriteLine(Remainder(str, R));}}// This code is contributed// by Subhadeep |
PHP
<?php// PHP implementation to find Remainder// when a large Number is divided by R// Function to Return Remainderfunction Remainder($str, $R){ // len is variable to store the // length of Number string. $len = strlen($str); $Num = 0; $Rem = 0; // loop that find Remainder for ($i = 0; $i < $len; $i++) { $Num = $Rem * 10 + ($str[$i] - '0'); $Rem = $Num % $R; } // Return the remainder return $Rem;}// Driver code// Get the large number as string$str = "13589234356546756";// Get the divisor R$R = 13;// Find and print the remainderecho Remainder($str, $R);// This code is contributed // by Akanksha Rai(Abby_akku) |
Output
11
Complexity Analysis:
- Time Complexity: O(L) where L is the length of the string
- Auxiliary Space: O(1), since no extra space has been taken.
Another approach:
Approach
1. Define the large number as a string.
2. Define the value of r.
3. Initialize the remainder to 0.
4. Iterate over each digit of the number using a loop.
5. Convert the current digit from a character to an integer.
6. Update the remainder by applying the modulo operator to the digit and the current remainder.
7. Print the final remainder.
C++
#include <iostream>int main(){ // Define the large number as a string std::string number = "123456789123456789123456789123456789123456789"; // Define the value of r int r = 7; // Initialize the remainder to 0 int remainder = 0; // Iterate over each digit of the number for (int i = 0; i < number.length(); i++) { // Convert the digit from a character to an integer int digit = number[i] - '0'; // Update the remainder by applying the modulo // operator to the digit and the current remainder remainder = (remainder * 10 + digit) % r; } // Print the remainder std::cout << "The remainder when " << number << " is divided by " << r << " is " << remainder << "." << std::endl; return 0;} |
C
#include <stdio.h>int main() { // Define the large number as a string char number[] = "123456789123456789123456789123456789123456789"; // Define the value of r int r = 7; // Initialize the remainder to 0 int remainder = 0; // Iterate over each digit of the number for (int i = 0; number[i] != '\0'; i++) { // Convert the digit from a character to an integer int digit = number[i] - '0'; // Update the remainder by applying the modulo operator to the digit and the current remainder remainder = (remainder * 10 + digit) % r; } // Print the remainder printf("The remainder when %s is divided by %d is %d.\n", number, r, remainder); return 0;} |
Python3
# Define the large number as a stringnumber = "123456789123456789123456789123456789123456789"# Define the value of rr = 7# Initialize the remainder to 0remainder = 0# Iterate over each digit of the numberfor i in range(len(number)): # Convert the digit from a character to an integer digit = int(number[i]) # Update the remainder by applying the modulo # operator to the digit and the current remainder remainder = (remainder * 10 + digit) % r# Print the remainderprint(f"The remainder when {number} is divided by {r} is {remainder}.") |
Javascript
// Define the large number as a stringlet number = "123456789123456789123456789123456789123456789";// Define the value of rlet r = 7;// Initialize the remainder to 0let remainder = 0;// Iterate over each digit of the numberfor (let i = 0; i < number.length; i++) { // Convert the digit from a character to an integer let digit = parseInt(number.charAt(i)); // Update the remainder by applying the modulo // operator to the digit and the current remainder remainder = (remainder * 10 + digit) % r;}// Print the remainderconsole.log(`The remainder when ${number} is divided by ${r} is ${remainder}.`); |
Java
import java.math.BigInteger;public class Main { public static void main(String[] args) { // Define the large number as a string String number = "123456789123456789123456789123456789123456789"; // Define the value of r int r = 7; // Convert the string to a BigInteger BigInteger bigNumber = new BigInteger(number); // Compute the remainder when the BigInteger is // divided by r BigInteger remainder = bigNumber.remainder(BigInteger.valueOf(r)); // Print the remainder System.out.println("The remainder when " + number + " is divided by " + r + " is " + remainder + "."); }} |
C#
using System;class Program{ static void Main() { // Define the large number as a string string number = "123456789123456789123456789123456789123456789"; // Define the value of r int r = 7; // Initialize the remainder to 0 int remainder = 0; // Iterate over each digit of the number for (int i = 0; i < number.Length; i++) { // Convert the digit from a character to an integer int digit = number[i] - '0'; // Update the remainder by applying the modulo // operator to the digit and the current remainder remainder = (remainder * 10 + digit) % r; } // Print the remainder Console.WriteLine("The remainder when {0} is divided by {1} is {2}.", number, r, remainder); }} |
Output
The remainder when 123456789123456789123456789123456789123456789 is divided by 7 is 1.
Time complexity: O(n), where n is the number of digits in the large number.
Auxiliary Space: O(1), as we are only storing a few integers and a string of digits.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
