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