Sunday, May 4, 2014

Count the number of digits in the number

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 )))

Forgive me for that :P. Please post your comments if you have better idea.

References

0 comments:

Post a Comment