package beust.codingchallenge;

import java.util.HashSet;

import java.util.Set;

public class CC {

static final int MAX = 10 * 1000;

static Set set = new HashSet();

static int nbn = 0;

static int jump = 1, biggestJump = 0;

/**

* @param args

*/

public static void main(String[] args) {

long t0 = System.currentTimeMillis();

test();

long tf = System.currentTimeMillis() - t0;

System.out.println(tf + " ms");

}

public static void test() {

for(int i=1; i < MAX; i++) {

final String str = "" + i;

final int strLength = str.length();

set.clear();

for(int j=0; j < strLength; j++) {

set.add(str.charAt(j));

}

if (strLength == set.size()) {

System.out.println("> " + str);

nbn++;

if (jump > biggestJump) {

biggestJump = jump;

}

jump = 1;

} else {

jump++;

System.out.println("< " + str + ", jump = "+ jump);

}

} // for

System.out.println("nbn="+nbn);

System.out.println("jump="+jump);

}

}

It runs in 20 ms, the biggest jump is

**124**and the count is

**5274**

## 3 comments:

But, there is an easier solution to the total count of numbers, for 1 to 10,000:

I am going to do it from 1, to 9,999 as 10,000 is not part of it (4 0s):

How many 4 digits number can be made out of 0, 1, ..., 9 if no digit can repeat:

9 (9 choices for the first digit, no 0) * 9 (for the second) * 8 (third) * 7 (fourth) = 4,536

How many 3 digits number can be made out of 0, 1, ..., 9 if no digit can repeat:

9 (9 choices for the first digit, no 0) * 9 (for the second) * 8 (third) = 648

How many 2 digits number can be made out of 0, 1, ..., 9 if no digit can repeat:

9 (9 choices for the first digit, no 0) * 9 = 81

How many 1 digits number can be made out of 0, 1, ..., 9 if no digit can repeat:

9 (9 choices for the first digit, no 0) = 9 (0 excluded)

So the total count is 4,536 + 648 + 81 + 9 = 5,274

As for the biggest jump, it can only appear in the 4 digits one, so it is 10,000 - 9,876 = 124

(99xx, 9899, 9898, etc.. going down to 9,876)

Thierry

PS: also posted on Cedric's blog

Following my investigation, a "clever" solution, only valid when max is a multiple of 10: 1000, 10,000, 100,000....

Result is immediate:

public class CC2 {

static final int[] PCA = {

9,

9 * 9,

9 * 9 * 8,

9 * 9 * 8 * 7,

9 * 9 * 8 * 7 * 6,

9 * 9 * 8 * 7 * 6 * 5,

9 * 9 * 8 * 7 * 6 * 5 * 4,

9 * 9 * 8 * 7 * 6 * 5 * 4 * 3,

9 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2

};

static final int[] ST = {

9,

98,

987,

9876,

98765,

987654,

9876543,

98765432,

987654321

};

public static void main(String[] args) {

// 4 is up to 9999, 5 up to 99,999, 9 up to 999,999,999,

// Biggest is 9,876,543,210

int nbd = Integer.parseInt(args[0]);

int max = (int)Math.pow(10, nbd);

int nbt = 0;

for(int i=1; i <= nbd; i++) {

nbt += PCA[i-1];

}

int rjump = max - ST[nbd-1];

System.out.println("For Max "+ max);

System.out.println("Total Count Of Numbers: " + nbt);

System.out.println("Relative Jump: "+rjump);

}

}

Nice solution from CB:

http://crazybob.org/BeustSequence.java.html

Post a Comment