Program to find remainder when large number is divided by r

0 0 7 minutes read

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 Remainder
int 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 code
int 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 Remainder
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 code
int 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 R
 
class 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 Remainder
def 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 code
if __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 Remainder
function 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 string
var str = "13589234356546756";
// Get the divisor R
var R = 13;
// Find and print the remainder
document.write(Remainder(str, R));
 
// This code is contributed by noob2000.
</script>

C#

// C# implementation to find 
// Remainder when a large
// Number is divided by R
using System;
 
class 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[i] - '0');
        Rem = Num % R;
    }
 
    // Return the remainder
    return Rem;
}
 
// Driver code
public 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 Remainder
function 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 remainder
echo Remainder($str, $R);
 
// This code is contributed 
// by Akanksha Rai(Abby_akku)

Output

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 string
number = "123456789123456789123456789123456789123456789"
# Define the value of r
r = 7
 
# Initialize the remainder to 0
remainder = 0
 
# Iterate over each digit of the number
for 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 remainder
print(f"The remainder when {number} is divided by {r} is {remainder}.")

Javascript

// Define the large number as a string
let number = "123456789123456789123456789123456789123456789";
// Define the value of r
let r = 7;
 
// Initialize the remainder to 0
let remainder = 0;
 
// Iterate over each digit of the number
for (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 remainder
console.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 zambiatek!