*Update: I posted a wrap-up here*.

Here is an interesting coding challenge: write a counter function that counts from 1 to max but only returns numbers whose digits don’t repeat.

For example, part of the output would be:

- 8, 9, 10, 12 (11 is not valid)
- 98, 102, 103 (99, 100 and 101 are not valid)
- 5432, 5436, 5437 (5433, 5434 and 5435 are not valid)

Also:

- Display the biggest jump (in the sequences above, it’s 4: 98 -> 102)
- Display the total count of numbers
- Give these two values for max=10000

Post your solution in the comments or on your blog. All languages and all approaches (brute force or not) are welcome.

I’m curious to see if somebody can come up with a clever solution (I don’t have one)…

#1 by

dubekon June 28, 2008 - 1:08 amIn Ruby, brute-force, probably really slow:

(98..103).select { |x| x.to_s.size == x.to_s.split(//).uniq.size }

=> [98, 102, 103]

#2 by

szeryfon June 28, 2008 - 1:15 amPerl:

#!perl -wl

use strict;

use List::Util qw(reduce max);

use constant MAX => 10_000;

my @nums = grep !/(.).*\1/, 1..MAX;

my $count = @nums;

my $jump = 0;

reduce {$jump = max($jump, $b – $a); $b} @nums;

print “@nums”;

print “$count, $jump”;

#3 by szeryf on June 28, 2008 - 1:26 am

Ruby, same approach (dunno if you call it clever or brute):

#!ruby -w

MAX = 10_000;

nums = (1..MAX).reject {|num| num.to_s =~ /(.).*\1/}

count = nums.length

jump = 0

nums.inject(1) {|a, b| jump = [jump, b – a].max; b}

p nums, count, jump

#4 by szeryf on June 28, 2008 - 1:44 am

Python, same approach:

#!python

import re

MAX = 10000

r = re.compile(r'(.).*\1′)

nums = [x for x in range(1, MAX) if not r.search(str(x))]

count = len(nums)

jump = 0

last = 0

for x in nums :

jump = max(jump, x – last)

last = x

print nums

print count

print jump

BTW. Now I see I forgot to use precompilation of regexps in Perl and Ruby versions — to do this, add o after the regexp, i.e. /(.).*\1/o

#5 by

dirkfon June 28, 2008 - 2:05 amJavascript, approach based on regexp :

<script>

var max = 10000, count=jump=bigjump=0;

for(var i=1; i<=max; i++) {

jump++;

if(! /(\d).*\1/g.test(i) ) {

document.write(i+’ ‘+jump+’ ‘ +'<br />’);

bigjump = Math.max(jump,bigjump);

jump=0;

count++;

}

}

bigjump = Math.max(jump,bigjump);

document.write(‘Total count:’+count+'<br />Biggest jump:’+bigjump+'<br />’);

</script>

#6 by

Marc Logemannon June 28, 2008 - 2:15 amSounds like a Google interview question or something. Am far too tired to “work” on that, but its a funny puzzler.

Marc

#7 by

levi_hon June 28, 2008 - 2:16 amJava (I’m sorry for the lack of indentation, I couldn’t figure out how the system expects you to post code):

import java.io.PrintStream;

import java.util.LinkedList;

import java.util.List;

public class Test {

private final int start;

private final int end;

private List numbersWithoutRepeatingDigits;

private int biggestJump;

public Test(int start, int end) {

this.start = start;

this.end = end;

numbersWithoutRepeatingDigits = new LinkedList();

}

public void calculateResults() {

int previousNumber = 0;

for (int number = start; number 0);

return false;

}

public void displayResults(PrintStream out) {

out.printf(“Numbers up to %d without repeating digits (%d): %s%n”, end, numbersWithoutRepeatingDigits.size(), numbersWithoutRepeatingDigits);

out.printf(“Biggest jump: %d%n”, biggestJump);

}

public static void main(String… parameters) {

Test test = new Test(1, 10000);

test.calculateResults();

test.displayResults(System.out);

}

}

A Set solution seems to be twice as slow, a regex one about 11 times. Both are still fast enough for finding results between 1 and 10000, though.

#8 by

levi_hon June 28, 2008 - 2:24 amThe comment system also ate my generics and most of both the calculateResults and hasRepeatingDigit(int) methods… oh well. I published it at docs.google.com/Doc?id=dppnxf9_0gtzdzzfw

#9 by

Keith Henryon June 28, 2008 - 2:39 amC#3:

//this could also be a regex based func

Func isNonRepeat =

i =>

{

char[] digits = i.ToString().ToCharArray();

return digits.Distinct().Count() == digits.Length;

};

//get all the non-repeating nums

var nums =

from int i in Enumerable.Range( 1, 10000 )

where isNonRepeat( i )

select i;

int last = 1, gap = 0, count = 0;

foreach ( var i in nums )

{

gap = Math.Max( gap, i – last );

last = i;

count++;

}

Console.WriteLine( “count: {0,0}”, count );

Console.WriteLine( “max gap: {0,0}”, gap );

Still brute forcing to get the gaps, I’m not sure whether there’s a Linq expression for Last.

#10 by

Nils Kassubeon June 28, 2008 - 2:52 am// Groovy version. The readable version seems fast enough

final MAX = 10000

def candidates = (1..MAX).findAll {

it.toString().size() == it.toString().toList().unique().size()

}

def jump = 0

def last = 0

for (x in candidates) {

if (x-last > jump) {jump = x-last}

last = x

}

println “Number of candidates: $candidates.size – Biggest jump $jump”

#11 by

Kannan Karthaon June 28, 2008 - 4:59 amHere is one from me in Java.

May not be a smart one, but works … Regex was really slow. Apologies for the indentation problem.

public class GenrateNumbers {

static int jump = 0;

static int MAX = 10000;

public static void main(String[] args) {

int tempValue = 0;

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

String number = String.valueOf(i);

boolean flag = hasRepeatingNumber(number.toCharArray());

if(!flag){

System.out.println(number);

jump = jump < (i – tempValue) ? (i – tempValue) : jump;

tempValue = i;

}

}

System.out.println(“Jump: ” + jump);

}

private static boolean hasRepeatingNumber(char[] charArray) {

for (int j = 0; j < charArray.length; j++) {

for (int j2 = j+1; j2 < charArray.length; j2++) {

if(charArray[j] == charArray[j2]){

return true;

}

}

}

return false;

}

}

#12 by

Thierry Janaudyon June 28, 2008 - 5:57 amCedric,

Here is my not-clever solution: janaudy.com/weblog/

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

#13 by

Thierry Janaudyon June 28, 2008 - 5:58 amCedric,

Here is my not-clever solution: janaudy.com/weblog/

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

#14 by

Danon June 28, 2008 - 6:30 amThierry, your answer raises an important question. Is the biggest jump 124? Do we include the gap between 9876 and 10000 as a “jump” even though 10000 is not one of the values in the sequence?

#15 by

Danon June 28, 2008 - 6:34 amHere is my naive Haskell solution:

import List(nub)

— Predicate that returns True if a number contains no duplicate digits.

noDuplicateDigits :: Int -> Bool

noDuplicateDigits n = length (nub (digits)) == length digits

where digits = show n

values :: Int -> [Int]

values n = [x | x (Int, Int)

answer n = (length sequence, gap)

where sequence = values n

gap = maximum (zipWith subtract sequence (tail sequence))

#16 by

dimitrison June 28, 2008 - 6:50 amBrute force in Erlang without erlang library calls.

-module(count).

-compile(export_all).

to_digits(Number) ->

to_digits(Number, []).

to_digits(Number, List) when Number div 10 == 0 ->

[Number | List];

to_digits(Number, List) ->

to_digits(Number div 10, [Number rem 10 | List]).

test_to_digits() ->

[3] = to_digits(3),

[1,2] = to_digits(12),

[1,0,0] = to_digits(100).

in_list(Element, [Element|_T]) ->

true;

in_list(_Element, []) ->

false;

in_list(Element, [_H|T]) ->

in_list(Element, T).

test_in_list() ->

true = in_list(1,[1,2,3]),

true = in_list(2,[1,2,3]),

true = in_list(3,[1,2,3]),

false = in_list(0,[1,2,3]),

false = in_list(0,[]),

true = in_list(1,[1]).

unique_list([]) ->

true;

unique_list([H|T]) ->

case in_list(H,T) of

true ->

false;

false ->

unique_list(T)

end.

test_unique_list() ->

false = unique_list([1,1]),

true = unique_list([1,2]),

true = unique_list([1]),

false = unique_list([1,2,1]),

false = unique_list([2,1,1]),

false = unique_list([1,1,2]),

true = unique_list([1,2,3]).

count(From, Max) ->

Cons = fun(List,Element) -> [Element|List] end,

count(From, Max + 1, Cons, []).

count(Upto, Upto, _Fun, State) ->

State;

count(From, Upto, Fun, State) when From

case unique_list(to_digits(From)) of

true ->

count(From + 1, Upto, Fun, Fun(State,From));

false ->

count(From + 1, Upto, Fun, State)

end.

test_count() ->

[3,2,1] = count(1,3),

[12,10,9] = count(9,12),

[103,102,98,97] = count(97,103).

test_count4() ->

Counter = fun({List,Sum},Element) -> {[Element|List],Sum + 1} end,

{[12,10],2} = count(10,13,Counter,{[],0}),

4 = count(97,104,fun(Sum,_Element) -> Sum + 1 end,0),

GapFinder = fun({[H|_T]=List,MaxGap},Element) when Element – H > MaxGap ->

{[Element|List],Element – H};

({List,MaxGap},Element) ->

{[Element|List],MaxGap}

end,

{[103,102,98],4} = count(98,104,GapFinder,{[],0}).

challenge(Max) ->

Finder = fun({[H|_T]=List,MaxGap,Counter},Element) when Element – H >= MaxGap ->

% io:format(“Gap ~p from ~p to ~p~n”, [Element-H,H,Element]),

{[Element|List],Element – H,Counter + 1};

({List,MaxGap,Counter},Element) ->

{[Element|List],MaxGap,Counter + 1}

end,

{_,BiggestJump,CountOfNumbers} = count(1,Max+1,Finder,{[],0,0}),

{BiggestJump, CountOfNumbers}.

test_challenge() ->

{1,10} = challenge(10),

{2,90} = challenge(100),

{11,738} = challenge(1000),

{105,5274} = challenge(10000),

{1047,32490} = challenge(100000).

test() ->

test_to_digits(),

test_in_list(),

test_unique_list(),

test_count(),

test_count4(),

test_challenge(),

ok.

#17 by

Danon June 28, 2008 - 7:32 amI also posted my solution on my blog, because the comments and indentation were stripped here.

blog.uncommons.org/2008/06/28/cedrics-coding-challenge/

#18 by

DeWitton June 28, 2008 - 7:49 amThe following python generator also works:

(i for i in xrange(start, end) if len(str(i)) == len(set(str(i)))):

-DeWitt

#19 by

Keith Henryon June 28, 2008 - 8:43 amC#3 again, down to two Linq loops:

//get all the non-repeating nums, conv to array to make ordinal lookups quicker

int counter = 0;

var nums = (

from i in Enumerable.Range( 1, 10000 )

let digits = i.ToString().ToCharArray()

where digits.Distinct().Count() == digits.Length

select new { num = i, ordinal = counter++ }

).ToArray();

Console.WriteLine( “count: {0,0}”, nums.Length );

//get all the gaps, using array to loop up previous

var gaps =

from item in nums

let last = item.ordinal > 0 ? nums[item.ordinal – 1].num : 1

select item.num – last;

Console.WriteLine( “max gap: {0,0}”, gaps.Max() );

#20 by

Pete Kirkhamon June 28, 2008 - 9:37 amAnother python implementation at tincancamera.com which is somewhat coloured by my normal use of python (prototyping algorithms before porting them to C++ or Java). Both brute-force iterate and filter and a combinatorics approach; the combinatorics one is faster for big N, but slower for N < 2e6. For max = 10000, total 25277895; biggest jump 105, from 1098 to 1203.

Why doesn’t your url form allow h t t p

#21 by

Pete Kirkhamon June 28, 2008 - 9:39 amNo, I don’t want my email published on your web site. Please remove link.

#22 by

Anonymouson June 28, 2008 - 10:00 amA Scala version:

for (i <- 1 to 100000; s = i.toString; if HashSet[Char](s:_*).size == s.size) println(i)

#23 by

Eugene Kuleshovon June 28, 2008 - 10:36 amJava version (brute-force) without collections and nearly no memory allocation. http://www.jroller.com/eu/entry/cedric_s_coding_challenge

I wonder if it is possible to give an answer to “the biggest jump” question without iterating trough entire sequence.

Also, it would be interesting to check possibilities of parallelizing tasks, perhaps using Kilim or Doug Lea’s for/join framework.

#24 by

Eugene Kuleshovon June 28, 2008 - 10:39 amCedric, what is with your comment filter? it doesn’t allow to use “http” “colon” “slash” “slash” in the comment text and in the url field…

#25 by

Thierry Janaudyon June 28, 2008 - 10:40 amDan,

You are right. Cedric needs to clarify this point. It is no a ‘jump’ as per say, let’s call my jump a ‘relative jump’ and not an ‘absolute jump’.

#26 by

Mathieu Robinon June 28, 2008 - 11:06 amNon brute force, in python:

from collections import deque

BASE = 10

MAX = 10000

queue = deque(range(1, BASE))

max_gap = 0

count = 1

prev_n = 0

while len(queue) > 0:

__n = queue.popleft()

__max_gap = max(max_gap, n – prev_n)

__prev_n = n

__count += 1

__if n * BASE < MAX:

____has_digit = [False] * BASE

____k = n

____while k != 0:

______has_digit[k % BASE]= True

______k /= BASE

____for d, b in enumerate(has_digit):

______if not b:

________q = n * BASE + d

________queue.append(q)

print count, max_gap

Also results in 5275 numbers in the sequence, max gap of 105.

#27 by

Thierry Janaudyon June 28, 2008 - 11:29 amFollowing 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);

}

}

#28 by

Mathieu Robinon June 28, 2008 - 11:55 amSmall patch to my solution:

– 0 is not part of the sequence, so count is initialized at 0, not 1

– to make it work if MAX is not a power of BASE:

if q queue.append(q)

#29 by

Andres Almirayon June 28, 2008 - 2:28 pmWaiting for someone to post a solution using Fan

#30 by

Charles Milleron June 28, 2008 - 3:49 pmThis problem is so much easier to solve in binary.

#31 by

Ants Aasmaon June 28, 2008 - 4:08 pmA somewhat non-bruteforce functionally factored Python solution: pastebin.com/f63ce9880

#32 by

Ants Aasmaon June 28, 2008 - 4:09 pmSorry, pasted the wrong URL, the correct one is pastebin.com/f5cec4683

#33 by

Ed Davieson June 28, 2008 - 5:30 pmszeryf, in your Ruby solution (which is neat and quick, by the way) wouldn’t this

jump = 0

nums.inject(1) {|a, b| jump = [jump, b – a].max; b}

be more naturally expressed using each_cons(2) instead of inject with its “arbitrary” initial value and redundant return value?

#34 by

Erik Engbrechton June 28, 2008 - 6:30 pmI’ve got a heuristics based solution on my blog. It’s mildly slower than a brute-force solution for small n, and I bet it’s competitive with a combinatronics based solution for large n.

I would post a link, but your comment filter will just eat it.

#35 by

Cedricon June 28, 2008 - 6:49 pmEric’s heuristic solution is at erikengbrecht.blogspot.com/2008/06/cedrics-code-challenge.html

#36 by szeryf on June 28, 2008 - 11:44 pm

Ed Davies: sure, I forgot about each_cons. But the return value in inject is not redundant, it’s used as `a’ in next pair

Ruby version with each_cons:

#!ruby -w

require “enumerator”

MAX = 10_000

nums = (1..MAX).reject {|num| num.to_s =~ /(.).*\1/o}

count = nums.length

jump = 0

nums.each_cons(2) {|a, b| jump = [jump, b – a].max}

p nums, count, jump

#37 by

Logan Johnsonon June 29, 2008 - 12:51 amsolution based on searching the string space:

docs.google.com/View?docID=dhpjhcjh_14f9msp3c8

#38 by

Bob Leeon June 29, 2008 - 1:52 amHere’s a really simple and efficient Java implementation that can find all values up to 10,000,000,000 on my Mac Pro in about 0.7s (not counting println overhead): crazybob.org/BeustSequence.java.html

#39 by

Bob Leeon June 29, 2008 - 2:17 amMake that 0.6s after a slight refactoring.

#40 by

Samuel A. Falvo IIon June 29, 2008 - 2:19 amPlease find herein a version that satisfies the challenge as stated, written in ANSI Forth. *WARNING* — This blog strips whitespace. VERY annoying. If the Forth code is found to be hard to read, this is partly to blame.

10000 constant largest

: rdrop postpone r> postpone drop ; immediate

( a simple approximation of integer sets using bit-masks )

( good enough to satisfy the challenge )

: mask ( n — n’ ) 1 swap lshift ;

: union ( n a — ) swap mask over @ or swap ! ;

: intersects ( n a — f ) @ swap mask and ;

( the challenge solution proper )

variable seen-set

variable recurs-set

variable t

variable max-j

variable j

: digits ( n — c-addr u ) 0 <# #s #> ;

: digit ( c-addr u — c-addr u n ) over c@ [char] 0 – ;

: recurs ( n — ) seen-set intersects recurs-set @ or recurs-set ! ;

: seen ( n — ) seen-set union ;

: analyze ( c-addr u — ) seen-set off recurs-set off begin dup while digit dup recurs seen 1 /string repeat 2drop ;

: recur ( c-addr u — f ) analyze recurs-set @ ;

: unique ( n — n ) dup digits recur if 1 j +! rdrop exit then ; ( filters numbers for uniqueness )

: j0 ( — ) 1 j ! ;

: initialize ( — ) t off j0 max-j off ;

: jumps ( — ) j @ max-j @ max max-j ! j0 ;

: total ( — ) 1 t +! ;

: stats ( — ) jumps total ;

: number ( n — n ) unique dup u. cr stats ;

: report ( — ) max-j @ . .” max jump” cr t @ . .” total numbers displayed” cr ;

: numbers ( — ) 1 begin number 1+ dup largest > until drop ;

: challenge ( — ) initialize numbers report ;

challenge

bye

To execute, paste the above code into “challenge.fs”, then execute “gforth challenge.fs” from the shell prompt.

#41 by

davidon June 29, 2008 - 3:20 amAnother Scala approach

class Counter(lower:Int, upper:Int) {

printMaxGapAndCount(filterDuplicates(new Range(lower, upper, 1)))

def hasNoDuplicate(charvals:Array[Char]):Boolean = {

charvals.takeWhile(charval => charvals.filter(el => el == charval).size == 1).size == charvals.size

}

def filterDuplicates(range:Range):List[Int] = {

range.toList.filter(num => hasNoDuplicate(num.toString.toArray))

}

def printMaxGapAndCount(list:List[Int]) = {

println(“count: ” + list.size + “, max gap: ” + list.map(el => list.dropWhile(num => num x > y).head)

}

}

new Counter(1,10000) results in count: 5274, max gap: 105 after about 5 minutes

#42 by

The real Mr. Funkon June 29, 2008 - 3:24 amAS3:

private const powers : Array = [ 1, 2, 4, 8, 16, 32, 64, 128, 256, 512 ];

private function doIt(max : Number) : void {

max = Math.min(max,999999999);

outer: for (var i : Number = 1; i 0) {

var remainder : uint = tmp % 10;

if (digits & powers[remainder])

continue outer;

digits += powers[remainder];

tmp /= 10;

}

trace(i);

}

}

#43 by

The real Mr. Funkon June 29, 2008 - 3:26 amRepost in html

private const powers : Array = [ 1, 2, 4, 8, 16, 32, 64, 128, 256, 512 ];

private function doIt(max : Number) : void {

max = Math.min(max,999999999);

outer: for (var i : Number = 1; i < max; i++) {

var tmp : uint = i;

var digits : uint = 0;

while (tmp > 0) {

var remainder : uint = tmp % 10;

if (digits & powers[remainder])

continue outer;

digits += powers[remainder];

tmp /= 10;

}

trace(i);

}

}

#44 by

Boni Gopalanon June 29, 2008 - 4:16 amWriting of the program was very simple with Java. The answer with 10K as the max limit is , a Jump of 124 : The jump from 9876 to 10K, a jump of 123 nos (All numbers from 9877 to 10000 are excluded hence a jump of 123). It was interesting to look at how the gap progression happened. There is a clear pattern and with this knowledge one can very trivially predict the biggest gap for numbers as big as google

______________________________________________

The following is the test results of how the gap progression happened for a range of 1 to 1000000000

——————————————————-

T E S T S

——————————————————-

Running com.boni.challenge.service.TestSeriesGenerator

Lower:1, Higher :2 Difference :1

Lower:10, Higher :12 Difference :2

Lower:98, Higher :102 Difference :4

Lower:109, Higher :120 Difference :11

Lower:987, Higher :1023 Difference :36

Lower:1098, Higher :1203 Difference :105

Lower:9876, Higher :10234 Difference :358

Lower:10987, Higher :12034 Difference :1047

Lower:98765, Higher :102345 Difference :3580

Lower:109876, Higher :120345 Difference :10469

Lower:987654, Higher :1023456 Difference :35802

Lower:1098765, Higher :1203456 Difference :104691

Lower:9876543, Higher :10234567 Difference :358024

Lower:10987654, Higher :12034567 Difference :1046913

Lower:98765432, Higher :102345678 Difference :3580246

Lower:109876543, Higher :120345678 Difference :10469135

Lower:987654321, Higher :1000000000 Difference :12345679

Tests run: 2, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 41.883 sec

Results :

Tests run: 2, Failures: 0, Errors: 0, Skipped: 0

————————————————————————

BUILD SUCCESSFUL

————————————————————————

Total time: 44 seconds

Finished at: Sun Jun 29 16:44:34 GMT+05:30 2008

Final Memory: 16M/289M

————————————————————————

______________________________________________

#45 by

Assen Kolovon June 29, 2008 - 6:32 amA fast non-trivial readable Java solution is published on docs.google.com/Doc?id=ddn32vzw_25dqbrq2c4

With printing all numbers is commented out, it executes in 430ms on a MacBook.

The trick is to generate only the next good number – starting from the end see which is the first digit that can be incremented, then fill the rest with the smallest allowed number.

#46 by

DavidLGon June 29, 2008 - 7:53 amScala code that only visits valid numbers:

def numsWithDigits(len: Int, digs: Set[Char], leading:Boolean): Iterator[List[Char]] = {

if (len == 0) Iterator.single(Nil)

else {

for (c <- (if (leading) digs-‘0’+’ ‘ else digs).elements;

n <- numsWithDigits(len-1, digs-c, leading && c==’ ‘)) yield c :: n;

}

}

val nums = (for (x <- numsWithDigits(4, scala.collection.immutable.TreeSet((‘0′ to ‘9’).toList:_*), true);

str = x.mkString.trim if str.length > 0;

n = str.toInt if n > 0) yield n).toList;

printf(“Count: %d\n”, nums.length);

val (first, second, gap) =

nums.zip(nums.tail).map { case (x,y) => (x,y, y-x) }.reduceLeft((a,b)=>if (a._3 > b._3) a else b);

printf(“Biggest gap is %d between %d and %d\n”, gap, first, second);

#47 by

ravemanon June 29, 2008 - 8:37 amnice idea, however its pretty easy

#48 by

Bob Leeon June 29, 2008 - 11:05 amI further simplified and sped up my implementation. It’s down to 330ms for max=10,000,000,000. It recursively iterates through all possible values for each digit.

crazybob.org/BeustSequence.java.html

#49 by

Bob Leeon June 29, 2008 - 12:57 pmOut of curiosity, I ported my solution to C: crazybob.org/beust.c.html

Even when compiled using “gcc -O3″, the C version takes 532ms while the Java version only takes 475ms (335ms if you subtract Java startup time).

#50 by

chrisbon June 29, 2008 - 12:59 pmBrute force, 44ms on my 1.8 lappy:

Func include = i => {

var chars = i.ToString().ToCharArray();

return chars.Distinct().Count() == chars.Length;

};

var sequence = Enumerable.Range(1, 10000).Where(i => include(i)).ToArray();

var gap = sequence.Skip(1).Select((i, j) => i – sequence[j]).Max();

Console.WriteLine(“Count: {0,0}”, sequence.Length);

Console.WriteLine(“Max Gap: {0,0}”, gap);