Lesson

11.10Count Total Digits

Problem Statement

Count the total number of digits in a given number.

Given a positive integer, determine how many digits it contains.

Example Inputs

Input: 1000
Output: 4
Input: 12345
Output: 5

Brute Force Approach

Approach

The brute force method involves converting the number to a string and counting its length. This straightforward approach leverages the built-in capabilities of programming languages to handle strings.

Steps

Convert the number to a string: This allows us to easily access each digit.
Count the number of characters in the string: Each character represents a digit in the number.
Return the count: This count is the total number of digits.

Time & Space Complexity

Time Complexity: O(n)
The time taken grows linearly with the number of digits, as each digit is processed once.
Space Complexity: O(n)
Additional space is used to store the string representation of the number, which has the same number of characters as digits.

Code Snippet

Dry Run

Input: 12345

Convert to string: "12345"
Count characters: 5
Return count: 5

Efficient Approach

Approach

An efficient method avoids converting the number to a string. Instead, it repeatedly divides the number by 10 until it becomes zero, counting the number of divisions. This approach uses mathematical operations to determine the digit count.

Steps

Initialize a count variable to 0.
Handle the edge case where the number is 0: Since 0 has one digit.
While the number is greater than 0:
- Divide the number by 10 using integer division.
- Increment the count by 1.
Return the count: This count represents the total number of digits.

Time & Space Complexity

Time Complexity: O(n)
Similar to the brute force method, the time taken grows linearly with the number of digits.
Space Complexity: O(1)
Only a fixed amount of additional space is used, regardless of the number's size.

Code Snippet

Dry Run

Input: 1000

Initialize count: 0
First division: 1000 / 10 = 100 → count 1
Second division: 100 / 10 = 10 → count 2
Third division: 10 / 10 = 1 → count 3
Fourth division: 1 / 10 = 0 → count 4
Return count: 4

Complexity Analysis

Brute Force Time & Space

Time Complexity: O(n)
Processes each digit once by converting the number to a string.
Space Complexity: O(n)
Stores the string representation of the number.

Optimized Time and Space

Time Complexity: O(n)
Processes each digit through division without converting to a string.
Space Complexity: O(1)
Uses a constant amount of additional space regardless of input size.

Conclusion

When solving the problem of counting the number of digits in a given number, both brute force and efficient approaches have their merits. The brute force method is simple and easy to implement, especially for beginners, as it leverages string manipulation. However, the efficient approach is more optimal in terms of space, as it avoids converting the number to a string and uses only basic arithmetic operations. Understanding both methods provides a solid foundation for tackling similar problems and highlights the importance of choosing the right approach based on the constraints and requirements.

Previous Next