Given a number find the number of odd digits in the number.
Odd digits are those which when divided with 2 leaves a remainder 1.
Example 1
Input: n = 45231
Output: 3
Explanation: The odd digits are 5, 3, and 1, so the count is 3.
Example 2
Input: n = 2048
Output: 0
Explanation: All digits are even, so there are no odd digits in the number.
Approach
The first observation is that checking whether a digit is odd is very easy. A digit is odd if it leaves remainder 1 when divided by 2, or more safely in code, if it is not divisible by 2.
The next observation is that the easiest digit to access in a number is always the last one. For example, in 45231, the last digit is 1. After removing it, the number becomes 4523, whose last digit is 3. This pattern keeps repeating until no digits are left.
That leads directly to the idea: keep taking the last digit, check whether it is odd, increase the answer when needed, and then remove that digit from the number.
Algorithm
First, make the number positive by taking its absolute value. This is done because only the digits matter here, not the minus sign.
Handle the case
N = 0separately by returning0, because the digit0is not odd and the usual loop would not run even once.Keep a variable
countas0. In the beginning, no odd digit has been found yet.Repeatedly take the last digit using
% 10.Check whether that digit is odd by testing
digit % 2 != 0. This condition works because odd digits are exactly the ones that are not divisible by2.If the digit is odd, increase
countby1.Remove the last digit using integer division by
10.Keep doing this until the number becomes
0, then returncount.
Key Points
If
N = 0, the answer is0because0is an even digit.If negative numbers are allowed, count the digits of the absolute value.
Dry Run
Count Odd Digits in a Number Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Returns how many digits in n are odd. */ int countOddDigits(int n) { // Uses the absolute value because only the digits matter here. long long num = llabs((long long)n); // The digit 0 is even, so the answer is 0 in this special case. if (num == 0) { return 0; } // Stores how many odd digits have been found so far. int count = 0; // Keep checking digits until the number becomes empty. while (num > 0) { // Extract the current last digit of the number. int digit = num % 10; // Increase the answer only when the current digit is odd. if (digit % 2 != 0) { count++; } // Remove the digit that has already been checked. num /= 10; } return count; }};// Driver code startsint main() { int n = 45231; Solution obj; cout << obj.countOddDigits(n) << endl; return 0;}Complexity Analysis
Time Complexity: O(log10 N), because one digit is processed in each iteration.
Space Complexity: O(1), because constant space is used.
Interview follow-up Questions
% 10 gives the last digit of a number, so it is the easiest way to inspect digits one by one.
Be the first to add a comment.