Sunday, May 4, 2014

Problem

Given the integer, find the number of digits in the integer.

Solution

Method 1 - Brute force using loop
Keep 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 )))
```