**Objective**

25 years ago, a British computer magazine had a programming contest and this was one of the puzzles.

There are a large number of 9 digit integers in the range *123456789* to *987654321* where each digit only appears once. What is the *100,000th* number in this sequence?

**Example**

The first number is *123456789*, the second is *123456798*, the third is *123456879* and so on. No digit can repeat so 122345675 is not a valid number in this sequence.

The problem was “Write a program that outputs the *100,000th* number as fast as possible. Use any algorithm, except you cannot pre-calculate the answer and then write a program that just prints the result. Your entry must calculate the number!”. This ran through June 2007

**Approach**

I am sure this has something to do with permutation, but I could not figure out the same. I went ahead with simple brute-force approach.

1. Iterate over the range *123456789* to *987654321*

2. Get all the digits of the number

3. Store each digit into a set and check for uniqueness

4. If the digit is *0* ignore that number

5. If the digit is repeated ignore that number.

Here is my first **Java** version

package avdongre.bcm.puzzle;
import java.util.HashSet;
import java.util.Set;
public class Solution {
public static void main(String[] args) {
long start = java.util.Calendar.getInstance().getTimeInMillis();
Set<Character> uniqueCheckSet = new HashSet<Character>();
int counter = 0;
boolean solutionFound = false;
for (int i = 123456789; i < 987654321; i++) {
if ( solutionFound ) {
break;
}
char[] digits = String.valueOf(i).toCharArray();
boolean validNumber = true;
for (int j = 0; j < digits.length; j++) {
if (digits[j] == '0') {
validNumber = false;
break;
}
if ( false == uniqueCheckSet.add(digits[j])) {
validNumber = false;
break;
}
}
if (validNumber) {
counter++;
if ( counter == 100000) {
System.out.println(i);
solutionFound = true;
}
}
uniqueCheckSet.clear();
}
long end = java.util.Calendar.getInstance().getTimeInMillis();
System.out.println("it took this long to complete this stuff: " + ((end - start) * 0.001) + " seconds");
}
}

This code took around 35 seconds to finish.

My friend force me to try the same for C++, but we come up with new approach of not using set but simple array in which if the digit is already seen the just set the value to 1 and continue.

With Optimization flag on following C++ code took around **3 seconds** to finish

#include <iostream>
#include <vector>
using namespace std;
int main(int argc, char ** argv) {
int counter = 0;
bool solutionFound = false;
std::vector<int> set(10);
for (int i = 123456789; i < 987654321; ++i) {
if ( solutionFound ) {
break;
}
int temp = i;
bool validNumber = true;
std::fill(set.begin(), set.end(), 0);
while (temp)
{
int digit = temp % 10;
if (digit == 0) {
validNumber = false;
break;
}
if ( set[digit] == 0 ) {
set[digit] = 1;
} else {
validNumber = false;
break;
}
temp /= 10;
}
if (validNumber) {
counter++;
if ( counter == 100000) {
cout << i << endl;
solutionFound = true;
}
}
}
}

Done the same with java and it has dramatically improved performance to **5 seconds**

package avdongre.bcm.puzzle;
import java.util.Arrays;
public class Solution {
public static void main(String[] args) {
long start = java.util.Calendar.getInstance().getTimeInMillis();
int[] set = new int[10];
int counter = 0;
boolean solutionFound = false;
for (int i = 123456789; i < 987654321; i++) {
if (solutionFound) {
break;
}
Arrays.fill(set, 0);
int temp = i;
boolean validNumber = true;
while (temp != 0) {
int digit = temp % 10;
if (digit == 0) {
validNumber = false;
break;
}
if (set[digit] == 0) {
set[digit] = 1;
} else {
validNumber = false;
break;
}
temp /= 10;
}
if (validNumber) {
counter++;
if (counter == 100000) {
System.out.println(i);
solutionFound = true;
}
}
}
long end = java.util.Calendar.getInstance().getTimeInMillis();
System.out.println("it took this long to complete this stuff: "
+ ((end - start) * 0.001) + " seconds");
}
}