Given two non-negative integers a and b, find the remainder when a is divided by b.
Assume b is not 0.
Example 1
Input: a = 17, b = 5
Output: 2
Explanation: 17 = 5 * 3 + 2, so the remainder is 2.
Example 2
Input: a = 24, b = 6
Output: 0
Explanation: 24 is exactly divisible by 6, so nothing is left over.
Approach
The small observation is very direct: the remainder is exactly what the modulo operator gives. So there is no need to simulate division, subtraction, or any longer process. Simply return the modulo a % b.
Algorithm
Check whether
bis0because division by zero is not valid.If
bis0, return-1in this implementation to show that the input is invalid.Otherwise compute
a % b, this gives the remainder.Return that value as the remainder.
Dry Run
Find Remainder Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Returns the remainder when a is divided by b. */ int findRemainder(int a, int b) { // Division by zero is not valid, so return -1 for invalid input. if (b == 0) { return -1; } // This stores the leftover part after dividing a by b. int remainder = a % b; return remainder; }};// Driver code startsint main() { Solution sol; int a = 17; int b = 5; cout << sol.findRemainder(a, b) << "\n"; return 0;}Complexity Analysis
Time Complexity: O(1) because the answer is found using one modulo operation.
Space Complexity: O(1) because constant space is used.
Interview follow-up Questions
The remainder becomes the first number itself. For example, 3 % 5 = 3.
Be the first to add a comment.