Problem
Given the integer, find the number of digits in the integer.
Solution
Method 1 - Brute force using loopKeep dividing the number, until it is 0. This will give us the count of number.
Java code
public static int getSize(long number) { int count = 0; while (number > 0) { count += 1; number = (number / 10); } return count; }
Method 2 - Convert to string
int length = String.valueOf(number).length();
Method 3 - Log and floor
digits = floor( log10( number ) ) + 1;
ie. in java
int length = (int)(Math.log10(number)+1);
Also, note that number > 0 , as we can't take log of negative numbers.
Time complexity - O(n)
These all are O(n) solution. Can we do better?
Method 4 - Divide and conquer
We know that numbers have limits, and also when we do integer division, result tends to some int or 0 if divisor is greater than dividend.
So, lets use it to our advantage:
n = 1; if (i >= 100000000){i /= 100000000; n += 8;} if (i >= 10000){i /= 10000; n += 4;} if (i >= 100){i /= 100; n += 2;} if (i >= 10){i /= 10; n += 1;}
Here is a long but beautiful java code borrowed from here:
if (n < 100000) { // 5 or less if (n < 100) { // 1 or 2 if (n < 10) return 1; else return 2; } else { // 3 or 4 or 5 if (n < 1000) return 3; else { // 4 or 5 if (n < 10000) return 4; else return 5; } } } else { // 6 or more if (n < 10000000) { // 6 or 7 if (n < 1000000) return 6; else return 7; } else { // 8 to 10 if (n < 100000000) return 8; else { // 9 or 10 if (n < 1000000000) return 9; else return 10; } } }
Of-course we can make it compact if we use ?: ternary operator, below is the code upto 7 digits
return (n < 100000 ? (n < 100 ? (n < 10 ? 1 : 2) : (n < 1000 ? 3 : (n < 10000 ? 4 : 5))) : (n < 10000000 ? 6 : (n < 10000000 : 7 )))
Forgive me for that :P. Please post your comments if you have better idea.
References
- http://stackoverflow.com/questions/1306727/way-to-get-number-of-digits-in-an-int
- http://stackoverflow.com/questions/6655754/finding-the-number-of-digits-of-an-integer
0 comments:
Post a Comment