Way to get number of digits in an int?
JavaIntegerJava Problem Overview
Is there a neater way for getting the number of digits in an int than this method?
int numDigits = String.valueOf(1000).length();
Java Solutions
Solution 1 - Java
Your String-based solution is perfectly OK, there is nothing "un-neat" about it. You have to realize that mathematically, numbers don't have a length, nor do they have digits. Length and digits are both properties of a physical representation of a number in a specific base, i.e. a String.
A logarithm-based solution does (some of) the same things the String-based one does internally, and probably does so (insignificantly) faster because it only produces the length and ignores the digits. But I wouldn't actually consider it clearer in intent - and that's the most important factor.
Solution 2 - Java
The logarithm is your friend:
int n = 1000;
int length = (int)(Math.log10(n)+1);
NB: only valid for n > 0.
Solution 3 - Java
The fastest approach: divide and conquer.
Assuming your range is 0 to MAX_INT, then you have 1 to 10 digits. You can approach this interval using divide and conquer, with up to 4 comparisons per each input. First, you divide [1..10] into [1..5] and [6..10] with one comparison, and then each length 5 interval you divide using one comparison into one length 3 and one length 2 interval. The length 2 interval requires one more comparison (total 3 comparisons), the length 3 interval can be divided into length 1 interval (solution) and a length 2 interval. So, you need 3 or 4 comparisons.
No divisions, no floating point operations, no expensive logarithms, only integer comparisons.
Code (long but fast):
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;
}
}
}
Benchmark (after JVM warm-up) - see code below to see how the benchmark was run:
- baseline method (with String.length): 2145ms
- log10 method: 711ms = 3.02 times as fast as baseline
- repeated divide: 2797ms = 0.77 times as fast as baseline
- divide-and-conquer: 74ms = 28.99
times as fast as baseline
Full code:
public static void main(String[] args) throws Exception {
// validate methods:
for (int i = 0; i < 1000; i++)
if (method1(i) != method2(i))
System.out.println(i);
for (int i = 0; i < 1000; i++)
if (method1(i) != method3(i))
System.out.println(i + " " + method1(i) + " " + method3(i));
for (int i = 333; i < 2000000000; i += 1000)
if (method1(i) != method3(i))
System.out.println(i + " " + method1(i) + " " + method3(i));
for (int i = 0; i < 1000; i++)
if (method1(i) != method4(i))
System.out.println(i + " " + method1(i) + " " + method4(i));
for (int i = 333; i < 2000000000; i += 1000)
if (method1(i) != method4(i))
System.out.println(i + " " + method1(i) + " " + method4(i));
// work-up the JVM - make sure everything will be run in hot-spot mode
allMethod1();
allMethod2();
allMethod3();
allMethod4();
// run benchmark
Chronometer c;
c = new Chronometer(true);
allMethod1();
c.stop();
long baseline = c.getValue();
System.out.println(c);
c = new Chronometer(true);
allMethod2();
c.stop();
System.out.println(c + " = " + StringTools.formatDouble((double)baseline / c.getValue() , "0.00") + " times as fast as baseline");
c = new Chronometer(true);
allMethod3();
c.stop();
System.out.println(c + " = " + StringTools.formatDouble((double)baseline / c.getValue() , "0.00") + " times as fast as baseline");
c = new Chronometer(true);
allMethod4();
c.stop();
System.out.println(c + " = " + StringTools.formatDouble((double)baseline / c.getValue() , "0.00") + " times as fast as baseline");
}
private static int method1(int n) {
return Integer.toString(n).length();
}
private static int method2(int n) {
if (n == 0)
return 1;
return (int)(Math.log10(n) + 1);
}
private static int method3(int n) {
if (n == 0)
return 1;
int l;
for (l = 0 ; n > 0 ;++l)
n /= 10;
return l;
}
private static int method4(int n) {
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;
}
}
}
}
private static int allMethod1() {
int x = 0;
for (int i = 0; i < 1000; i++)
x = method1(i);
for (int i = 1000; i < 100000; i += 10)
x = method1(i);
for (int i = 100000; i < 1000000; i += 100)
x = method1(i);
for (int i = 1000000; i < 2000000000; i += 200)
x = method1(i);
return x;
}
private static int allMethod2() {
int x = 0;
for (int i = 0; i < 1000; i++)
x = method2(i);
for (int i = 1000; i < 100000; i += 10)
x = method2(i);
for (int i = 100000; i < 1000000; i += 100)
x = method2(i);
for (int i = 1000000; i < 2000000000; i += 200)
x = method2(i);
return x;
}
private static int allMethod3() {
int x = 0;
for (int i = 0; i < 1000; i++)
x = method3(i);
for (int i = 1000; i < 100000; i += 10)
x = method3(i);
for (int i = 100000; i < 1000000; i += 100)
x = method3(i);
for (int i = 1000000; i < 2000000000; i += 200)
x = method3(i);
return x;
}
private static int allMethod4() {
int x = 0;
for (int i = 0; i < 1000; i++)
x = method4(i);
for (int i = 1000; i < 100000; i += 10)
x = method4(i);
for (int i = 100000; i < 1000000; i += 100)
x = method4(i);
for (int i = 1000000; i < 2000000000; i += 200)
x = method4(i);
return x;
}
Again, benchmark:
- baseline method (with String.length): 2145ms
- log10 method: 711ms = 3.02 times as fast as baseline
- repeated divide: 2797ms = 0.77 times as fast as baseline
- divide-and-conquer: 74ms = 28.99 times as fast as baseline
Edit
After I wrote the benchmark, I took a sneak peak into Integer.toString from Java 6, and I found that it uses:
final static int [] sizeTable = { 9, 99, 999, 9999, 99999, 999999, 9999999,
99999999, 999999999, Integer.MAX_VALUE };
// Requires positive x
static int stringSize(int x) {
for (int i=0; ; i++)
if (x <= sizeTable[i])
return i+1;
}
I benchmarked it against my divide-and-conquer solution:
- divide-and-conquer: 104ms
- Java 6 solution - iterate and compare: 406ms
Mine is about 4x as fast as the Java 6 solution.
Solution 4 - Java
Two comments on your benchmark: Java is a complex environment, what with just-in-time compiling and garbage collection and so forth, so to get a fair comparison, whenever I run a benchmark, I always: (a) enclose the two tests in a loop that runs them in sequence 5 or 10 times. Quite often the runtime on the second pass through the loop is quite different from the first. And (b) After each "approach", I do a System.gc() to try to trigger a garbage collection. Otherwise, the first approach might generate a bunch of objects, but not quite enough to force a garbage collection, then the second approach creates a few objects, the heap is exhausted, and garbage collection runs. Then the second approach is "charged" for picking up the garbage left by the first approach. Very unfair!
That said, neither of the above made a significant difference in this example.
With or without those modifications, I got very different results than you did. When I ran this, yes, the toString approach gave run times of 6400 to 6600 millis, while the log approach topok 20,000 to 20,400 millis. Instead of being slightly faster, the log approach was 3 times slower for me.
Note that the two approaches involve very different costs, so this isn't totally shocking: The toString approach will create a lot of temporary objects that have to be cleaned up, while the log approach takes more intense computation. So maybe the difference is that on a machine with less memory, toString requires more garbage collection rounds, while on a machine with a slower processor, the extra computation of log would be more painful.
I also tried a third approach. I wrote this little function:
static int numlength(int n)
{
if (n == 0) return 1;
int l;
n=Math.abs(n);
for (l=0;n>0;++l)
n/=10;
return l;
}
That ran in 1600 to 1900 millis -- less than 1/3 of the toString approach, and 1/10 the log approach on my machine.
If you had a broad range of numbers, you could speed it up further by starting out dividing by 1,000 or 1,000,000 to reduce the number of times through the loop. I haven't played with that.
Solution 5 - Java
Can't leave a comment yet, so I'll post as a separate answer.
The logarithm-based solution doesn't calculate the correct number of digits for very big long integers, for example:
long n = 99999999999999999L;
// correct answer: 17
int numberOfDigits = String.valueOf(n).length();
// incorrect answer: 18
int wrongNumberOfDigits = (int) (Math.log10(n) + 1);
Solution 6 - Java
Using Java
int nDigits = Math.floor(Math.log10(Math.abs(the_integer))) + 1;
use import java.lang.Math.*; in the beginning
Using C
int nDigits = floor(log10(abs(the_integer))) + 1;
use inclue math.h in the beginning
Solution 7 - Java
Since the number of digits in base 10 of an integer is just 1 + truncate(log10(number)), you can do:
public class Test {
public static void main(String[] args) {
final int number = 1234;
final int digits = 1 + (int)Math.floor(Math.log10(number));
System.out.println(digits);
}
}
Edited because my last edit fixed the code example, but not the description.
Solution 8 - Java
Another string approach. Short and sweet - for any integer n.
int length = ("" + n).length();
Solution 9 - Java
Marian's solution adapted for long type numbers (up to 9,223,372,036,854,775,807), in case someone want's to Copy&Paste it. In the program I wrote this for numbers up to 10000 were much more probable, so I made a specific branch for them. Anyway it won't make a significative difference.
public static int numberOfDigits (long n) {
// Guessing 4 digit numbers will be more probable.
// They are set in the first branch.
if (n < 10000L) { // from 1 to 4
if (n < 100L) { // 1 or 2
if (n < 10L) {
return 1;
} else {
return 2;
}
} else { // 3 or 4
if (n < 1000L) {
return 3;
} else {
return 4;
}
}
} else { // from 5 a 20 (albeit longs can't have more than 18 or 19)
if (n < 1000000000000L) { // from 5 to 12
if (n < 100000000L) { // from 5 to 8
if (n < 1000000L) { // 5 or 6
if (n < 100000L) {
return 5;
} else {
return 6;
}
} else { // 7 u 8
if (n < 10000000L) {
return 7;
} else {
return 8;
}
}
} else { // from 9 to 12
if (n < 10000000000L) { // 9 or 10
if (n < 1000000000L) {
return 9;
} else {
return 10;
}
} else { // 11 or 12
if (n < 100000000000L) {
return 11;
} else {
return 12;
}
}
}
} else { // from 13 to ... (18 or 20)
if (n < 10000000000000000L) { // from 13 to 16
if (n < 100000000000000L) { // 13 or 14
if (n < 10000000000000L) {
return 13;
} else {
return 14;
}
} else { // 15 or 16
if (n < 1000000000000000L) {
return 15;
} else {
return 16;
}
}
} else { // from 17 to ...¿20?
if (n < 1000000000000000000L) { // 17 or 18
if (n < 100000000000000000L) {
return 17;
} else {
return 18;
}
} else { // 19? Can it be?
// 10000000000000000000L is'nt a valid long.
return 19;
}
}
}
}
}
Solution 10 - Java
How about plain old Mathematics? Divide by 10 until you reach 0.
public static int getSize(long number) {
int count = 0;
while (number > 0) {
count += 1;
number = (number / 10);
}
return count;
}
Solution 11 - Java
Can I try? ;)
based on Dirk's solution
final int digits = number==0?1:(1 + (int)Math.floor(Math.log10(Math.abs(number))));
Solution 12 - Java
Marian's Solution, now with Ternary:
public int len(int n){
return (n<100000)?((n<100)?((n<10)?1:2):(n<1000)?3:((n<10000)?4:5)):((n<10000000)?((n<1000000)?6:7):((n<100000000)?8:((n<1000000000)?9:10)));
}
Because we can.
Solution 13 - Java
I see people using String libraries or even using the Integer class. Nothing wrong with that but the algorithm for getting the number of digits is not that complicated. I am using a long in this example but it works just as fine with an int.
private static int getLength(long num) {
int count = 1;
while (num >= 10) {
num = num / 10;
count++;
}
return count;
}
Solution 14 - Java
no String API, no utils, no type conversion, just pure java iteration ->
public static int getNumberOfDigits(int input) {
int numOfDigits = 1;
int base = 1;
while (input >= base * 10) {
base = base * 10;
numOfDigits++;
}
return numOfDigits;
}
You can go long for bigger values if you please.
Solution 15 - Java
Curious, I tried to benchmark it ...
import org.junit.Test;
import static org.junit.Assert.*;
public class TestStack1306727 {
@Test
public void bench(){
int number=1000;
int a= String.valueOf(number).length();
int b= 1 + (int)Math.floor(Math.log10(number));
assertEquals(a,b);
int i=0;
int s=0;
long startTime = System.currentTimeMillis();
for(i=0, s=0; i< 100000000; i++){
a= String.valueOf(number).length();
s+=a;
}
long stopTime = System.currentTimeMillis();
long runTime = stopTime - startTime;
System.out.println("Run time 1: " + runTime);
System.out.println("s: "+s);
startTime = System.currentTimeMillis();
for(i=0,s=0; i< 100000000; i++){
b= number==0?1:(1 + (int)Math.floor(Math.log10(Math.abs(number))));
s+=b;
}
stopTime = System.currentTimeMillis();
runTime = stopTime - startTime;
System.out.println("Run time 2: " + runTime);
System.out.println("s: "+s);
assertEquals(a,b);
}
}
the results are :
Run time 1: 6765 s: 400000000 Run time 2: 6000 s: 400000000
Now I am left to wonder if my benchmark actually means something but I do get consistent results (variations within a ms) over multiple runs of the benchmark itself ... :) It looks like it's useless to try and optimize this...
edit: following ptomli's comment, I replaced 'number' by 'i' in the code above and got the following results over 5 runs of the bench :
Run time 1: 11500 s: 788888890 Run time 2: 8547 s: 788888890Run time 1: 11485 s: 788888890 Run time 2: 8547 s: 788888890
Run time 1: 11469 s: 788888890 Run time 2: 8547 s: 788888890
Run time 1: 11500 s: 788888890 Run time 2: 8547 s: 788888890
Run time 1: 11484 s: 788888890 Run time 2: 8547 s: 788888890
Solution 16 - Java
With design (based on problem). This is an alternate of divide-and-conquer. We'll first define an enum (considering it's only for an unsigned int).
public enum IntegerLength {
One((byte)1,10),
Two((byte)2,100),
Three((byte)3,1000),
Four((byte)4,10000),
Five((byte)5,100000),
Six((byte)6,1000000),
Seven((byte)7,10000000),
Eight((byte)8,100000000),
Nine((byte)9,1000000000);
byte length;
int value;
IntegerLength(byte len,int value) {
this.length = len;
this.value = value;
}
public byte getLenght() {
return length;
}
public int getValue() {
return value;
}
}
Now we'll define a class that goes through the values of the enum and compare and return the appropriate length.
public class IntegerLenght {
public static byte calculateIntLenght(int num) {
for(IntegerLength v : IntegerLength.values()) {
if(num < v.getValue()){
return v.getLenght();
}
}
return 0;
}
}
The run time of this solution is the same as the divide-and-conquer approach.
Solution 17 - Java
What about this recursive method?
private static int length = 0;
public static int length(int n) {
length++;
if((n / 10) < 10) {
length++;
} else {
length(n / 10);
}
return length;
}
Solution 18 - Java
simple solution:
public class long_length {
long x,l=1,n;
for (n=10;n<x;n*=10){
if (x/n!=0){
l++;
}
}
System.out.print(l);
}
Solution 19 - Java
A really simple solution:
public int numLength(int n) {
for (int length = 1; n % Math.pow(10, length) != n; length++) {}
return length;
}
Solution 20 - Java
Or instead the length you can check if the number is larger or smaller then the desired number.
public void createCard(int cardNumber, int cardStatus, int customerId) throws SQLException {
if(cardDao.checkIfCardExists(cardNumber) == false) {
if(cardDao.createCard(cardNumber, cardStatus, customerId) == true) {
System.out.println("Card created successfully");
} else {
}
} else {
System.out.println("Card already exists, try with another Card Number");
do {
System.out.println("Enter your new Card Number: ");
scan = new Scanner(System.in);
int inputCardNumber = scan.nextInt();
cardNumber = inputCardNumber;
} while(cardNumber < 95000000);
cardDao.createCard(cardNumber, cardStatus, customerId);
}
}
}
Solution 21 - Java
I haven't seen a multiplication-based solution yet. Logarithm, divison, and string-based solutions will become rather unwieldy against millions of test cases, so here's one for ints:
/**
* Returns the number of digits needed to represents an {@code int} value in
* the given radix, disregarding any sign.
*/
public static int len(int n, int radix) {
radixCheck(radix);
// if you want to establish some limitation other than radix > 2
n = Math.abs(n);
int len = 1;
long min = radix - 1;
while (n > min) {
n -= min;
min *= radix;
len++;
}
return len;
}
In base 10, this works because n is essentially being compared to 9, 99, 999... as min is 9, 90, 900... and n is being subtracted by 9, 90, 900...
Unfortunately, this is not portable to long just by replacing every instance of int due to overflow. On the other hand, it just so happens it will work for bases 2 and 10 (but badly fails for most of the other bases). You'll need a lookup table for the overflow points (or a division test... ew)
/**
* For radices 2 &le r &le Character.MAX_VALUE (36)
*/
private static long[] overflowpt = {-1, -1, 4611686018427387904L,
8105110306037952534L, 3458764513820540928L, 5960464477539062500L,
3948651115268014080L, 3351275184499704042L, 8070450532247928832L,
1200757082375992968L, 9000000000000000000L, 5054470284992937710L,
2033726847845400576L, 7984999310198158092L, 2022385242251558912L,
6130514465332031250L, 1080863910568919040L, 2694045224950414864L,
6371827248895377408L, 756953702320627062L, 1556480000000000000L,
3089447554782389220L, 5939011215544737792L, 482121737504447062L,
839967991029301248L, 1430511474609375000L, 2385723916542054400L,
3902460517721977146L, 6269893157408735232L, 341614273439763212L,
513726300000000000L, 762254306892144930L, 1116892707587883008L,
1617347408439258144L, 2316231840055068672L, 3282671350683593750L,
4606759634479349760L};
public static int len(long n, int radix) {
radixCheck(radix);
n = abs(n);
int len = 1;
long min = radix - 1;
while (n > min) {
len++;
if (min == overflowpt[radix]) break;
n -= min;
min *= radix;
}
return len;
}
Solution 22 - Java
We can achieve this using a recursive loop
public static int digitCount(int numberInput, int i) {
while (numberInput > 0) {
i++;
numberInput = numberInput / 10;
digitCount(numberInput, i);
}
return i;
}
public static void printString() {
int numberInput = 1234567;
int digitCount = digitCount(numberInput, 0);
System.out.println("Count of digit in ["+numberInput+"] is ["+digitCount+"]");
}
Solution 23 - Java
One wants to do this mostly because he/she wants to "present" it, which mostly mean it finally needs to be "toString-ed" (or transformed in another way) explicitly or implicitly anyway; before it can be presented (printed for example).
If that is the case then just try to make the necessary "toString" explicit and count the bits.
Solution 24 - Java
I wrote this function after looking Integer.java source code.
private static int stringSize(int x) {
final int[] sizeTable = {9, 99, 999, 9_999, 99_999, 999_999, 9_999_999,
99_999_999, 999_999_999, Integer.MAX_VALUE};
for (int i = 0; ; ++i) {
if (x <= sizeTable[i]) {
return i + 1;
}
}
}
Solution 25 - Java
One of the efficient ways to count the number of digits in an int variable would be to define a method digitsCounter with a required number of conditional statements.
The approach is simple, we will be checking for each range in which a n digit number can lie:
0 : 9 are Single digit numbers
10 : 99 are Double digit numbers
100 : 999 are Triple digit numbers and so on...
static int digitsCounter(int N)
{ // N = Math.abs(N); // if `N` is -ve
if (0 <= N && N <= 9) return 1;
if (10 <= N && N <= 99) return 2;
if (100 <= N && N <= 999) return 3;
if (1000 <= N && N <= 9999) return 4;
if (10000 <= N && N <= 99999) return 5;
if (100000 <= N && N <= 999999) return 6;
if (1000000 <= N && N <= 9999999) return 7;
if (10000000 <= N && N <= 99999999) return 8;
if (100000000 <= N && N <= 999999999) return 9;
return 10;
}
A cleaner way to do this is to remove the check for the lower limits as it won't be required if we proceed in a sequential manner.
static int digitsCounter(int N)
{
N = N < 0 ? -N : N;
if (N <= 9) return 1;
if (N <= 99) return 2;
if (N <= 999) return 3;
if (N <= 9999) return 4;
if (N <= 99999) return 5;
if (N <= 999999) return 6;
if (N <= 9999999) return 7;
if (N <= 99999999) return 8;
if (N <= 999999999) return 9;
return 10; // Max possible digits in an 'int'
}
Solution 26 - Java
Here's a really simple method I made that works for any number:
public static int numberLength(int userNumber) {
int numberCounter = 10;
boolean condition = true;
int digitLength = 1;
while (condition) {
int numberRatio = userNumber / numberCounter;
if (numberRatio < 1) {
condition = false;
} else {
digitLength++;
numberCounter *= 10;
}
}
return digitLength;
}
The way it works is with the number counter variable is that 10 = 1 digit space. For example .1 = 1 tenth => 1 digit space. Therefore if you have int number = 103342; you'll get 6, because that's the equivalent of .000001 spaces back. Also, does anyone have a better variable name for numberCounter? I can't think of anything better.
Edit: Just thought of a better explanation. Essentially what this while loop is doing is making it so you divide your number by 10, until it's less than one. Essentially, when you divide something by 10 you're moving it back one number space, so you simply divide it by 10 until you reach <1 for the amount of digits in your number.
Here's another version that can count the amount of numbers in a decimal:
public static int repeatingLength(double decimalNumber) {
int numberCounter = 1;
boolean condition = true;
int digitLength = 1;
while (condition) {
double numberRatio = decimalNumber * numberCounter;
if ((numberRatio - Math.round(numberRatio)) < 0.0000001) {
condition = false;
} else {
digitLength++;
numberCounter *= 10;
}
}
return digitLength - 1;
}