Find N % 4 (Remainder with 4) for a large value of N
Given a string str representing a large integer, the task is to find the result of N % 4.
Examples:
Input: N = 81
Output: 1
Input: N = 46234624362346435768440
Output: 0
Recommended: Please try your approach on {IDE} first, before moving on to the solution.
Approach: The remainder of division by 4 is dependent on only the last 2 digits of a number, so instead of dividing N we divide only the last two digits of N and find the remainder.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return s % n int findMod4(string s, int n) { // To store the number formed by // the last two digits int k; // If it contains a single digit if (n == 1) k = s[0] - '0' ; // Take last 2 digits else k = (s[n - 2] - '0' ) * 10 + s[n - 1] - '0' ; return (k % 4); } // Driver code int main() { string s = "81" ; int n = s.length(); cout << findMod4(s, n); return 0; } |
Java
// Java implementation of the approach class GFG { // Function to return s % n static int findMod4(String s, int n) { // To store the number formed by // the last two digits int k; // If it contains a single digit if (n == 1 ) k = s.charAt( 0 ) - '0' ; // Take last 2 digits else k = (s.charAt(n - 2 ) - '0' ) * 10 + s.charAt(n - 1 ) - '0' ; return (k % 4 ); } // Driver code public static void main(String[] args) { String s = "81" ; int n = s.length(); System.out.println(findMod4(s, n)); } } // This code is contributed by Code_Mech. |
Python3
# Python 3 implementation of the approach # Function to return s % n def findMod4(s, n): # To store the number formed by # the last two digits # If it contains a single digit if (n = = 1 ): k = ord (s[ 0 ]) - ord ( '0' ) # Take last 2 digits else : k = (( ord (s[n - 2 ]) - ord ( '0' )) * 10 + ord (s[n - 1 ]) - ord ( '0' )) return (k % 4 ) # Driver code if __name__ = = '__main__' : s = "81" n = len (s) print (findMod4(s, n)) # This code is contributed by # Surendra_Gangwar |
C#
// C# implementation of the approach using System; class GFG { // Function to return s % n static int findMod4( string s, int n) { // To store the number formed by // the last two digits int k; // If it contains a single digit if (n == 1) k = s[0] - '0' ; // Take last 2 digits else k = (s[n - 2]- '0' ) * 10 + s[n - 1] - '0' ; return (k % 4); } // Driver code public static void Main() { string s = "81" ; int n = s.Length; Console.WriteLine(findMod4(s, n)); } } // This code is contributed by Code_Mech. |
Javascript
<script> // Javascript implementation of the approach // Function to return s % n function findMod4(s, n) { // To store the number formed by // the last two digits var k=0; // If it contains a single digit if (n == 1) k = s[0] - '0' ; // Take last 2 digits else k = (s[n - 2] - '0' ) * 10 + s[n - 1] - '0' ; return (k % 4); } // Driver code var s = "81" ; var n = s.length; document.write(findMod4(s, n)); // This code is contributed by nood2000. </script> |
PHP
<?php // PHP implementation of the approach // Function to return s % n function findMod4( $s , $n ) { // To store the number formed by // the last two digits $k ; // If it contains a single digit if ( $n == 1) $k = $s [0] - '0' ; // Take last 2 digits else $k = ( $s [ $n - 2] - '0' ) * 10 + $s [ $n - 1] - '0' ; return ( $k % 4); } // Driver code { $s = "81" ; $n = strlen ( $s ); echo (findMod4( $s , $n )); } // This code is contributed by Code_Mech. |
Output
1
Time Complexity: O(1)
Approach: Using Bitwise Operators
Steps:
- The input number is read as a string.
- The string is converted to an integer using a loop that iterates over each character of the string.
- Updates the integer by multiplying it by 10 and adding the value of the current digit.
- The remainder of the integer n divided by 4 is found using the bitwise AND operator & and the number 3, which is equal to 0b11 in binary.
- This operation keeps only the two least significant bits of the integer, which represent the remainder when divided by 4.
- Last, print the remainder.
Below is implementation of the above approach:
C++
#include <iostream> #include <string> using namespace std; int main() { string str= "81" ; // Convert the string to an integer unsigned long long n = 0; for ( char c : str) { n = n * 10 + (c - '0' ); } // Find the remainder of n divided by 4 using bitwise AND int remainder = n & 3; cout << remainder << endl; return 0; } |
Java
public class Main { public static void main(String[] args) { String str = "81" ; // Convert the string to a long long n = 0 ; for ( char c : str.toCharArray()) { n = n * 10 + (c - '0' ); } // Find the remainder of n divided by 4 using bitwise AND int remainder = ( int ) (n & 3 ); System.out.println(remainder); } } |
Python3
str = "81" # Convert the string to an integer n = 0 for c in str : n = n * 10 + int (c) # Find the remainder of n divided by 4 using bitwise AND remainder = n & 3 print (remainder) |
C#
using System; namespace ConsoleApp { class GFG { static void Main( string [] args) { string str = "81" ; // Convert the string to a long integer ulong n = 0; foreach ( char c in str) { n = n * 10 + ( ulong )(c - '0' ); } // Find the remainder of n divided by 4 using bitwise AND int remainder = ( int )(n & 3); Console.WriteLine(remainder); } } } |
Javascript
// Define the input string let str = "81" ; // Initialize a variable to store the converted number let n = 0; // Convert the string to a number for (let i = 0; i < str.length; i++) { // Multiply the current result by 10 and add the numeric value of the character n = n * 10 + parseInt(str[i]); } // Find the remainder of n divided by 4 using bitwise AND let remainder = n & 3; // Print the remainder console.log(remainder); |
Output
1
Time Complexity: O(n), where n is the number of digits in the input string
Auxiliary Space: O(1)
Contact Us