How to Efficiently Return the Max Possible Integer With a Given Number of Digits

How to print the largest number in a more efficient way? (Beginner Java)

int largest = Integer.MIN_VALUE;
int value = 0;
for (int i = 0; i <= 4; i++) {
    value = input.nextInt();
    if (value > largest) {
        largest = value;
    }
}
System.out.println(largest);

1. Input 5 values
2. On each input, compare it with the largest variable.
3. Efficient because it doesn't have any additional overhead of sorting or collection api

Count number of digits - which method is most efficient?

The following is even more efficient:

int findn(int num)
{
   if ( num < 10 )
      return 1;
   if ( num < 100 )
      return 2;
   //continue until max int
}

You could optimize this even further by doing a binary search, but that would be overkill.

Efficient way to determine number of digits in an integer

Well, the most efficient way, presuming you know the size of the integer, would be a lookup. Should be faster than the much shorter logarithm based approach. If you don't care about counting the '-', remove the + 1.

#include <climits>

// generic solution
template <class T>
int numDigits(T number)
{
    int digits = 0;
    if (number < 0) digits = 1; // remove this line if '-' counts as a digit
    while (number) {
        number /= 10;
        digits++;
    }
    return digits;
}

// partial specialization optimization for 64-bit numbers
template <>
int numDigits(int64_t x) {
    if (x == INT64_MIN) return 19 + 1;
    if (x < 0) return digits(-x) + 1;

    if (x >= 10000000000) {
        if (x >= 100000000000000) {
            if (x >= 10000000000000000) {
                if (x >= 100000000000000000) {
                    if (x >= 1000000000000000000)
                        return 19;
                    return 18;
                }
                return 17;
            }
            if (x >= 1000000000000000)
                return 16;
            return 15;
        } 
        if (x >= 1000000000000) {
            if (x >= 10000000000000)
                return 14;
            return 13;
        }
        if (x >= 100000000000)
            return 12;
        return 11;
    }
    if (x >= 100000) {
        if (x >= 10000000) {
            if (x >= 100000000) {
                if (x >= 1000000000)
                    return 10;
                return 9;
            }
            return 8;
        }
        if (x >= 1000000)
            return 7;
        return 6;
    }
    if (x >= 100) {
        if (x >= 1000) {
            if (x >= 10000)
                return 5;
            return 4;
        }
        return 3;
    }
    if (x >= 10)
        return 2;
    return 1;
}

// partial specialization optimization for 32-bit numbers
template<>
int numDigits(int32_t x)
{
    if (x == INT32_MIN) return 10 + 1;
    if (x < 0) return numDigits(-x) + 1;

    if (x >= 10000) {
        if (x >= 10000000) {
            if (x >= 100000000) {
                if (x >= 1000000000)
                    return 10;
                return 9;
            }
            return 8;
        }
        if (x >= 100000) {
            if (x >= 1000000)
                return 7;
            return 6;
        }
        return 5;
    }
    if (x >= 100) {
        if (x >= 1000)
            return 4;
        return 3;
    }
    if (x >= 10)
        return 2;
    return 1;
}

// partial-specialization optimization for 8-bit numbers
template <>
int numDigits(char n)
{
    // if you have the time, replace this with a static initialization to avoid
    // the initial overhead & unnecessary branch
    static char x[256] = {0};
    if (x[0] == 0) {
        for (char c = 1; c != 0; c++)
            x[c] = numDigits((int32_t)c);
        x[0] = 1;
    }
    return x[n];
}

Given n, find the maximum numbers added to get n

I was about to post the answer but @Cruise Liu beat me to it. Ill try explaining it a bit .
Its a type of integer partitioning but you dont need to generate the elements since you're only interested in the 'number of elements'. i.e. the final answer 3 and not {1, 2, 3}

Given a number N, you have another restriction that numbers cannot repeat.
Hence the best case would be if N is actually a number say 1, 3, 6, 10, 15

i.e. f(x) = x * (x + 1) / 2. 

For example, take 6. f(x) = 6 exists. specifically f(3) = 6 . Thus you get the answer 3.

What this means is that if there is an integer X that exists for f(x) = N, then there is a set of numbers 1, 2, 3 ... x that when added up give N. And this is the maximum number possible (without repitition).

However, there are cases in f(x) = N where x is not an integer.

f(x) = x * (x + 1 ) / 2 = N
i.e. x**2 + x = 2*N
x**2 + x - 2*N = 0

Solving this quadratic we get

Since the number x is not negative we can't have

So we're left with

For N = 6

A perfect Integer. But for N = 12

which is 8.845 / 2 which is a fraction. The floor value is 4, which is the answer.

In short: Implement a function
f(N) = (int) ((-1.0 + sqrt(1 + 8*N))/2.0 )

i.e.

int max_partition_length(int n){
    return (int)((-1.0 + sqrt(1 + n*8))/2);
}

Why is Git Bash not using the correct Java path as defined in the PATH environment variable?

Check if you have some old java.exe, javaw.exe, javaws.exe in the c:/windows/system32 folder, as mentioned in "Java path..Error of jvm.cfg".

I just checked with Git 2.6.3 on Windows, where I don't have anything in c:/windows/system32, and the result is consistent between:

git bash:

vonc@bigvonc MINGW64 /
$ java -version
java version "1.7.0_51"
Java(TM) SE Runtime Environment (build 1.7.0_51-b13)
Java HotSpot(TM) 64-Bit Server VM (build 24.51-b03, mixed mode)

and CMD:

C:\prgs\git\PortableGit-2.6.3-64-bit>java -version
java version "1.7.0_51"
Java(TM) SE Runtime Environment (build 1.7.0_51-b13)
Java HotSpot(TM) 64-Bit Server VM (build 24.51-b03, mixed mode)

Both report the same java at the same spot:

vonc@bigvonc MINGW64 /
$ which java
/c/prgs/jdk/jdk-7u51-windows-x64/bin/java

C:\prgs\git\PortableGit-2.6.3-64-bit>which java.exe
C:\prgs\jdk\jdk-7u51-windows-x64\bin\java.exe

Conclusion: upgrade to the latest git for windows.

How do you set java version in windows git bash?

You don't set the java version. You are seeking the $PATH (bash) and the %PATH% (Windows/DOS/cmd.exe) environment variables. When you run the command java -version, the shell searches the directories on the $PATH to locate the java program and run it with the given arguments. If you get different results in different shells then that means you have different PATHs such that a different installation of Java is found.

---

Related Topics