2
\$\begingroup\$

I have to find the thousandth number (excluding numbers 3, 4, 7) but it's taking a long time, about 9 seconds. I'd like to find out how to improve performance.

import java.sql.Date;
import java.text.DecimalFormat;
import java.text.SimpleDateFormat;

public class FirstChallange {

    private static int removedNumbers;
    private static int numberQuantity;
    private static int lastNumberFound; 
    private static int cont;
    private static int pos3;
    private static int pos4;
    private static int pos7;    

    public static void main(String[] args) 
    { 

        long inicio = System.currentTimeMillis();  

        removedNumbers = 0;
        numberQuantity = 10000000;


        for (cont = 1; removedNumbers <= numberQuantity; cont++) {      
            String str = new String(); 
            str = String.valueOf(cont);     

            pos3 = str.indexOf("3");
            pos4 = str.indexOf("4");
            pos7 = str.indexOf("7");

            if((pos3 == -1) && (pos4 == -1) && (pos7 == -1)) {
                removedNumbers++; 
                if(removedNumbers == numberQuantity){ // can not find numbers (3, 4, 7)
                    lastNumberFound = cont; 
                }
            } 
        }       

        DecimalFormat dfmt = new DecimalFormat("0");

        System.out.println(dfmt.format(lastNumberFound)); 

        long fim  = System.currentTimeMillis();   
        System.out.println(new SimpleDateFormat("ss.SSS").format(new Date(fim - inicio)));  


    }
}

Is converting numbers into string and removing them with indexOf the best mode? or is there anything better than indexOf like RabinKarp?

Expected result: 180999565 in 5/4 seconds

\$\endgroup\$
  • 1
    \$\begingroup\$ Could you clarify what your code is doing? Maybe using a smaller number example \$\endgroup\$ – dustytrash Apr 18 at 14:15
  • \$\begingroup\$ The code has the object to find the thousand number that does not contain 3, 4 or 7 \$\endgroup\$ – Sebastián Apr 18 at 14:38
  • \$\begingroup\$ What do you mean by 'the thousand number'? \$\endgroup\$ – dustytrash Apr 18 at 14:42
  • 2
    \$\begingroup\$ The thousandth positive integer whose base 10 representation doesn't contain 3, 4, or 7 is 2929. \$\endgroup\$ – Peter Taylor Apr 18 at 14:54
  • \$\begingroup\$ Seems like the program finds the 10 millionth number, which is a lot different than the 1 thousandth number in terms of how long a program like this would be expected to run. \$\endgroup\$ – JS1 Apr 19 at 1:08
3
\$\begingroup\$

I'm aware that another answer is already accepted, but my solution only takes 0.000022s and if I don't talk about it I will burst: ;-)

public class FirstChallange {
    static char[] mapChars = new char[0x40];
    static {
        mapChars['0'] = '0';
        mapChars['1'] = '1';
        mapChars['2'] = '2';
        mapChars['3'] = '5';
        mapChars['4'] = '6';
        mapChars['5'] = '8';
        mapChars['6'] = '9';
    }
    public final static void main(String[] args) {
        long nanoStart = System.nanoTime();
        int maxNumber = 10000000;
        char[] digits = Integer.toString(maxNumber, 7).toCharArray();
        for (int i = 0; i < digits.length; i++) {
            digits[i] = mapChars[digits[i]];
        }
        String lastNumber = new String(digits);
        long diffTime = System.nanoTime() - nanoStart;
        System.out.println(diffTime);
        NumberFormat dfmt = DecimalFormat.getNumberInstance();
        dfmt.setMaximumFractionDigits(6);
        System.out.println("last number: " + lastNumber);
        System.out.println("time: " + dfmt.format(diffTime / 1000000000d) + " s");
    }
}

Instead of brute forcing I'm making use of different bases. With three digits "forbidden" to be used, you essentially change your number base from 10 to 7, so instead of counting up a variable that is restricted to base 7 by skipping values that are outside it, you just do a conversion from one base to the other. You could do that by calculation yourself, but in order to get the correct value you need to do a remapping of the digits. The easiest way to do that is a string-replacemant, so I started with converting the decimal value to a String using the toString method that allows the specification of a radix.

This results to the text 150666343 that looks familiar to the expected result. If we forbid the digits 7, 8 and 9 that would already be the solution but in our case digits "in the middle" are forbidden, so in order to get the result for this different set of digits, we have to map the digits 3 and 4 to 5 and 6 and the digits 5 and 6 to 8 and 9.

That's it. Instead of iterating over a loop 180 million times you do it 9 times (plus some loops inside toCharArray, toString and new String(char).

\$\endgroup\$
5
\$\begingroup\$
import java.sql.Date;

You shouldn't need anything from java.sql unless you're using a relational database. java.util.Date would be more appropriate here (or nothing at all).


public class FirstChallange {

Challenge has one a and two es.

The name is not going to be very helpful in identifying the purpose of the class in six months' time, and there's no comment to say what the source of the challenge was either.


    private static int removedNumbers;
    private static int numberQuantity;
    private static int lastNumberFound; 
    private static int cont;
    private static int pos3;
    private static int pos4;
    private static int pos7;    

Variables should usually be in the narrowest scope possible. This means that static fields should be extremely rare.


        long inicio = System.currentTimeMillis();  

It's best to be consistent in the use of language: either name all the variables in Portuguese or name them all in English.

This line has trailing whitespace. If you can configure your IDE to automatically remove this, you will reduce the number of spurious changes which muddle revision control diffs.


        DecimalFormat dfmt = new DecimalFormat("0");

        System.out.println(dfmt.format(lastNumberFound)); 

That is heavily overkill for System.out.println(lastNumberFound);


        removedNumbers = 0;
        numberQuantity = 10000000;


        for (cont = 1; removedNumbers <= numberQuantity; cont++) {      
            String str = new String(); 
            str = String.valueOf(cont);     

            pos3 = str.indexOf("3");
            pos4 = str.indexOf("4");
            pos7 = str.indexOf("7");

Actually iterating over objects is rarely the best way to count them. Iteration with filtering even less so. If you spend some time thinking through the mathematics before you start writing code, there's an easy way to tackle this problem by base conversion which takes about 20 milliseconds.

\$\endgroup\$
3
\$\begingroup\$

I tried several different approaches and the problem is - string manipulation is just slower than arithmetic.

Note: I refactored the check into a function because it is good practice in that it creates smaller pieces of code whose functions are then more easily understood.

import java.sql.Date;
import java.text.DecimalFormat;
import java.text.SimpleDateFormat;

public class FirstChallenge {

    private static int lastNumberFound;

    public static void main(String[] args) 
    {
        long inicio = System.currentTimeMillis();

        int removedNumbers = 0;
        int numberQuantity = 10000000;

        int cont;
        for (cont = 1; removedNumbers <= numberQuantity; cont++) {
            if (go(cont)) {
                removedNumbers++;
                if(removedNumbers == numberQuantity){ // can not find numbers (3, 4, 7)
                    lastNumberFound = cont; 
                }
            }
        }       

        DecimalFormat dfmt = new DecimalFormat("0");

        System.out.println(dfmt.format(lastNumberFound));

        long fim  = System.currentTimeMillis();
        System.out.println(new SimpleDateFormat("ss.SSS").format(new Date(fim - inicio)));
    }

    private static boolean go(int i) {
        int j = i;
        while (j > 0) {
            int d = j % 10;
            if (d == 3 || d == 4 || d == 7) return false;
            j = j / 10;
        }
        return true;
    }
}

The result I got:

180999565
01.134

Notice that the time is less than 1/5th the time of the other algorithm.

\$\endgroup\$
  • \$\begingroup\$ And mine is less than 1/50,000th than yours ;-) \$\endgroup\$ – Lothar Apr 18 at 21:27
1
\$\begingroup\$

Do not instantiate a new String. There's no point as you set the value again on the next line anyway.

String str = String.valueOf(cont); 

Instead of going from 1 -> X and getting the last value, you could go from X -> 1 and get the first value found.

I strongly suggest renaming your variables to be more descriptive (English). It'll make it easier to understand what your code is accomplishing.

Instead of using indexOf() you could use contains(), although you'll have to do some testing to see if it the performance is better.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.