In Ruby, brute-force, probably really slow: (98..103).select { |x| x.to_s.size == x.to_s.split(//).uniq.size } => [98, 102, 103]

Perl: #!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";

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

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

Javascript, 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>

Sounds like a Google interview question or something. :) Am far too tired to "work" on that, but its a funny puzzler. Marc

Java (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.

The 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

C#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.

// 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"

Here 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; } }

Cedric, 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

Cedric, 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

Thierry, 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?

Here 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))

Brute 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.

I also posted my solution on my blog, because the comments and indentation were stripped here. blog.uncommons.org/2008/06/28/cedrics-coding-challenge/

The following python generator also works: (i for i in xrange(start, end) if len(str(i)) == len(set(str(i)))): -DeWitt

C#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() );

Another 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

No, I don't want my email published on your web site. Please remove link.

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

Java version (brute-force) without collections and nearly no memory allocation. 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.

Cedric, 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...

Dan, 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'.

Non 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.

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); } }

Small 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)

Waiting for someone to post a solution using Fan ;-)

This problem is so much easier to solve in binary.

A somewhat non-bruteforce functionally factored Python solution: pastebin.com/f63ce9880

Sorry, pasted the wrong URL, the correct one is pastebin.com/f5cec4683

szeryf, 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?

I'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.

Eric's heuristic solution is at erikengbrecht.blogspot.com/2008/06/cedrics-code-challenge.html

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

solution based on searching the string space: docs.google.com/View?docID=dhpjhcjh_14f9msp3c8

Here'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

Make that 0.6s after a slight refactoring.

Please 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.

Another 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

AS3: 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); } }

Repost 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);     } }

Writing 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 ------------------------------------------------------------------------ ______________________________________________

A 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.

Scala 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);

nice idea, however its pretty easy

I 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

Out 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).

Brute 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);

@chrisb: FWIW, that would take 12 hrs. for max=10,000,000,000.

I spent some time over the problem, with python. The result is linked below. Bob Lee might find this interesting, as there is a comparison with my implementation of his methods. ciju.wordpress.com/2008/06/29/beust-sequence-aka-sequence-of-numbers-without-repeating-digits/

OK, last time. I made mine a little longer, but clearer and faster: crazybob.org/BeustSequence.java.html @ciju: This implementation may help reduce the overhead you're seeing from method calls in Python.

OK, last last time. I went the other direction and made an alternate, more concise version: crazybob.org/BeustSequence2.java.html

A not very pretty but quite fast Java version: rifers.org/paste/show/7580 Time of 1 to 10,000,000 ~58ms on a very old Pentium 4. The test method could do to be a bit more comprehensive.

Tried my solution in C. It ran through the whole sequence in 180ms. The most important change is the use of integer to store the sequence, rather than string(originally, Bob's idea). @Bob: I tried implementing your method(BeustSequence2), in C. It took about 700ms. Again I am being partial of not trying to improve your code. Let me know if you would like to see the code, and suggest changes, although I assume we have spent too much time on this problem.

Forgot to mention. The performance results are for limit of 10,000,000,000(ex: all possible).

Created another (my last ;-)) version based on 'Permutations Listing': oogifu.blogspot.com/2008/06/coding-challenge-ii.html Runs the 10^9 one in .6 second.

There was a bug in the code :(. Current version runs in about 230ms($time ./a.out). ciju.wordpress.com/2008/06/29/beust-sequence-aka-sequence-of-numbers-without-repeating-digits/

This is a pretty fast solution using ascii-APL J (jsoftware.com). Experts from likely will write even more terse code f =: [:(#;[:>./2-~/\])(#~([:*/[:~:":)"0) f i. 10000 +----+---+ |5275|105| +----+---+

@ciju: BeustSequence2 is the slower but more concise version. I'd try BeustSequence. Then again, the C compiler may not optimize around the recursion very well.

Not really particularly cute or clever, but a solution in Lua that uses a coroutine that generates numbers as high as your implementation can count: local c = coroutine.create(function ()     local i = 0     while true do         while tostring(i):match("(%d).*%1") do             i = i + 1         end         coroutine.yield(i)         i = i + 1     end end) I'm sure it's not especially fast either.

public static void main(String[] args) { int max = 5437; for (int i = 0; i repeats = new HashSet(); for (int i = 0; i < str.length(); i++) { if (!repeats.add(str.substring(i, i + 1))) { return true; } } return false; }

Oops: public static void main(String[] args) { int max = 5437; for (int i = 0; i repeats = new HashSet(); for (int i = 0; i < str.length(); i++) { if (!repeats.add(str.substring(i, i + 1))) return true; } } return false; }

public static void main(String[] args) { int max = 5437; for (int i = 0; i < max; i++) { if (!hasRepeatingInteger(i + "")) { System.out.println(i + ""); } } } public static boolean hasRepeatingInteger(String str) { Set<String> repeats = new HashSet<String>(); for (int i = 0; i < str.length(); i++) { if (!repeats.add(str.substring(i, i + 1))) { return true; } } return false; }

Alright, I've settled on the shorter solution: crazybob.org/BeustSequence.java.html Here's the test harness which prints the count and largest gap: crazybob.org/TestBeustSequence.java.html And here's the shared Listener interface: crazybob.org/Listener.java.html

This is exactly the type of problem in which you want to avoid high level structures like Strings. Couldn't post the code so I put it in my google docs: docs.google.com/Doc?id=avjh8kg87sn_29d4p2gk35 My guess is this is about the fastest implementation you'll come up with unless someone codes it in C with pointers, and even then the JVM is probably close. To do large numbers be sure to comment out the println that prints a number every iteration. The one you requested: For a max of: 10000 Total Displayed=5274 Biggest Jump=104 A smallish one: For a max of: 1000000 Total Displayed=168570 Biggest Jump=10468 The largest power of 10 that executes instantly: For a max of: 10000000 Total Displayed=712890 Biggest Jump=104690 Big one still takes less than a minute: For a max of: 100000000 Total Displayed=2345850 Biggest Jump=1046912 The pattern on "Biggest Jump" seems strange. I suppose it's a power of 10 type thing. I could probably go up another power of 10 or two, but that would start to take minutes/hours and any higher than that and I'll have to change a few ints to longs.

Never mind--I hadn't seen Eugene's solution--keeping it all within ints improves the hell out of it as long as you aren't printing anything each iteration.

I think the sum of the values for n digits is (9!/(9-(n-1))!) * ( 45 * pow(10, n-1) + 40 * floor(pow(10, n-1) / 9) ) . Or the progression of the pattern in my blog. Empirically, the maximum jump for n digits is floor( ( 1203456789-1098765432 ) / pow(10, 10-n) ), since they all have much the same format. For the maximum below an arbitrary value, you'd test the 987... 1023... jump as well. Probably could think of an expression for a non-noughty number, but it's bed time. tincancamera.com/blog

@Bill Kress: Mine handles 10^10 in less than half a second.

factor-language.blogspot.com/2008/06/cedrics-code-challenge.html

Yeah, sorry. I started coding before reading the bottom 1/2 of the responses (the power solutions). I mostly feel strange about all the earlier solutions using higher language constructs to make a short (nloc) solution when that really doesn't help anyone. Even java String should be out of the consideration--let alone anything that actually manipulated their strings by splitting them apart just to compare them--holy cow that's inefficient. Also, all the solutions are brute force. The pattern of count of numbers found for each power of 10 leads me to believe there actually is a much faster mathematical solution than comparing digits. Probably some factorial-looking thing.

Another version of recursive approach - the similar with Crazy Bob's. I did a quick benchmark and it is faster. I'm not sure it is because I calculate bits and reuse them... public class Test { private static class ResultListener { public void foundResult(long result) { // System.out.println(result); } } static int BITS[]; static { BITS = new int[10]; BITS[0] = ( 1 = max ) return; for( int i = 0 ; i < 10; i++ ) { if ( (used & BITS[i]) == 0 ) { l.foundResult(start+i); recurseRetrieve( (start+i) * 10 , max, used | BITS[i], l ); } } } }

My bad. The above does not return in 1 to MAX in sequence. It is basically combinatorial approach so it will be ( 1 , 10 , 102, 1023 , 1203 )

As requested, I posted my solution on my blog. It's in OCaml, and finds all the values from 1 to max_int in 27 seconds on my 2.16 GHz MacBook Pro. enfranchisedmind.com/blog/2008/07/01/cedrics-problem-in-ocaml/

BTW, your blog software balks at if you prefix the URL with the HyperText Transfer Protocol prefix.

@Bill Kress I don't know what makes you feel that all solutions are brute force. At the least Bob's and my solutions are not. They just generate the required numbers(which the problem statement asks to generate). If you are talking about the count of such numbers, then thats altogether a different issue. Its simple permutation. Here's google helping us out with the answer for maximum possible such numbers. www.google.co.in/search?hl=en&q=9*(1+%2B+9!%2F8!+%2B+9!%2F7!+%2B+9!%2F6!+%2B+9!%2F5!+%2B+9!%2F4!+%2B+9!%2F3!+%2B+9!%2F2!+%2B+9!+%2B+9!) If you need explanation, visit the end of my blog entry. ciju.wordpress.com/2008/06/30/beust-sequence-aka-sequence-of-numbers-without-repeating-digits/ Note: the link has changed from the one posted before, I don't know what wordpress.com is doing.

I'm fascinated by the number of authors that claim their solution isn't brute force, when in fact the solution is clearly brute force (up to and including regex! A recompiled regex on every loop iteration! That's brute with a big, wooden club!) We may be watching the end of the era when programmers even cared about the performance of an algorithm and nowadays simply assume that the implementation that takes the fewest characters to write is the fastest one. We need a symposium on the definition of brute force.

Brute-force or not! Regarding the confusion about whats brute-force and whats not, let me explain a little. If you are asked to generate numbers form 1 to 10, generating those numbers is not brute-force. You have to go though them to print them out, at the least. Now, if you are asked to print numbers in range [1, 10] which are divisible by 5. Then checking each number and printing only the once divisible by 5 (ex: 5 and 10), does make it brute-force. Because the output length is 2, and you are going through whole of the search space to generate those 2 numbers. The one which only generates 5 and 10 is the _not_ brute-force method. And I can conform that at least Bob's and my method are not brute-force. They only generate the numbers which don't have repeated digits. They don't generate the whole sequence and check whether digits are repeated in a number. And thats why, for example, my solution completes in about 0.2s (I am talking about generating all the possibilities and only the possibilities, 8877690(see my comment above), in sequential order).

@Bill Kress: Something wrong with your algorithm: I could verify that your "Biggest Jump" is wrong for the 10,000 case. Here are my results: The one you requested: For a max of: 10,000 done in 0 ms Total Displayed: 5,274 Biggest Jump: 124 Biggest Jump begin: 9,877 Biggest Jump end : 10,000 @Crazy Bob: 414 ms ... yeah, I have fast hardware and yeah your code is cleaner! Huge Crazy Bob's one...: For a max of: 10,000,000,000 done in 414 ms Total Displayed: 8,877,690 Biggest Jump: 123,456,790 Biggest Jump begin: 9,876,543,211 Biggest Jump end : 10,000,000,000 @all: I just jump number ranges when most significant numbers have repetitions. The essentials (copy+paste on your IDE and format if you will): public class BeustLongSequenceFinder { private final long m_maxValue; private long m_maxContinuousSkippingCount; private long m_maxContinuousSkippingEnd; private long m_continuousSkippingCount; private long m_totalSkippingCount; public BeustLongSequenceFinder(final long maxValue) { if (maxValue 0"); m_maxValue = maxValue; } //... getters ... public void findNumbers() { // Result fields m_maxContinuousSkippingCount = 0; m_maxContinuousSkippingEnd = 0; m_totalSkippingCount = 0; // Calc. state fields m_continuousSkippingCount = 0; final long xNextVal = loopNext(0, m_maxValue, digitCount(m_maxValue) - 1, 0); if (0 != m_continuousSkippingCount) storeJump(xNextVal); } // end method findNumbers private final void storeJump(final long xNextVal) { m_totalSkippingCount += m_continuousSkippingCount; if (m_continuousSkippingCount > m_maxContinuousSkippingCount) { m_maxContinuousSkippingCount = m_continuousSkippingCount; m_maxContinuousSkippingEnd = xNextVal - 1; } } private final long loopNext(long nextValue, final long maxValue, final long digitIndex, final int leftmostMask) { if (0 == digitIndex) { for (int i = 0; (i maxValue) m_continuousSkippingCount += maxValue - nextValue + 1; else m_continuousSkippingCount += xSkipped; nextValue = xNextNextValue; } else { nextValue = loopNext(nextValue, maxValue, xNextIndex, leftmostMask | (1 << i)); } // end if-else } // end for } // end if-else return nextValue; } // end if-else } // end method loopDigit private static final long digitCount(final long num) { return (long) Math.log10(num) + 1; } // end method digitCount } // end class BeustSequenceFinder

Sorry! 2nd attempt giving HTML escaping to less-than and greater-than operators: public class BeustLongSequenceFinder { private final long m_maxValue; private long m_maxContinuousSkippingCount; private long m_maxContinuousSkippingEnd; private long m_continuousSkippingCount; private long m_totalSkippingCount; public BeustLongSequenceFinder(final long maxValue) { if (maxValue <= 0) throw new IllegalArgumentException("must be: maxValue > 0"); m_maxValue = maxValue; } //... getters ... public void findNumbers() { // Result fields m_maxContinuousSkippingCount = 0; m_maxContinuousSkippingEnd = 0; m_totalSkippingCount = 0; // Calc. state fields m_continuousSkippingCount = 0; final long xNextVal = loopNext(0, m_maxValue, digitCount(m_maxValue) - 1, 0); if (0 != m_continuousSkippingCount) storeJump(xNextVal); } // end method findNumbers private final void storeJump(final long xNextVal) { m_totalSkippingCount += m_continuousSkippingCount; if (m_continuousSkippingCount > m_maxContinuousSkippingCount) { m_maxContinuousSkippingCount = m_continuousSkippingCount; m_maxContinuousSkippingEnd = xNextVal - 1; } } private final long loopNext(long nextValue, final long maxValue, final long digitIndex, final int leftmostMask) { if (0 == digitIndex) { for (int i = 0; (i < 10) && (nextValue <= maxValue); ++i, ++nextValue) { if (0 != (leftmostMask & (1 << i))) ++m_continuousSkippingCount; else { if (0 != m_continuousSkippingCount) { storeJump(nextValue); m_continuousSkippingCount = 0; } } // end if-else } // end for return nextValue; } else { final long xNextIndex = digitIndex - 1; if (0 == leftmostMask) { nextValue = loopNext(nextValue, maxValue, xNextIndex, 0); // Leading 0 for (int i = 1; i < 10; i++) nextValue = loopNext(nextValue, maxValue, xNextIndex, (1 << i)); } else { for (int i = 0; (i < 10) && (nextValue <= maxValue); i++) { if (0 != (leftmostMask & (1 << i))) { // Digits already repeated // Skipping inner loops long xSkipped = 10; // = pow10(digitIndex); { for (int p = 1; p < digitIndex; ++p) xSkipped *= 10; } final long xNextNextValue = nextValue + xSkipped; if (xNextNextValue > maxValue) m_continuousSkippingCount += maxValue - nextValue + 1; else m_continuousSkippingCount += xSkipped; nextValue = xNextNextValue; } else { nextValue = loopNext(nextValue, maxValue, xNextIndex, leftmostMask | (1 << i)); } // end if-else } // end for } // end if-else return nextValue; } // end if-else } // end method loopNext private static final long digitCount(final long num) { return (long) Math.log10(num) + 1; } // end method digitCount } // end class BeustSequenceFinder

@sidereal: For max=10^10, 8,877,691 values match. My algorithm only performs 8,877,690 operations while the brute force approach requires 10^10 ops (or 1,125X more than mine).

@sidereal: To illustrate, here's a log2-scale graph of: 1) the # of ops performed by my algorithm 2) the # of ops performed by a brute force algorithm 3) the number of matching values for maximum values up to 10^10: crazybob.org/beust.png As you can see, a brute force algorithm scales at about O(max) while my algorithm scales at O(matches) in the worst case (and much better in common cases).

some ugly java code usage long from = Long.parseLong(args[0]); long to = Long.parseLong(args[1]); long last=-1; for(Udin z = new Udin(from); z.inc() && (last=z.toLong()) 0 || number==0){ int rem = (int) (num % 10); if(set.get(rem)){ throw new IllegalArgumentException( number + " is invalid 'cas "+rem+" exist in "+set ); } setDigit(++biggest, rem); num = num / 10; if(number==0){ break; } } Arrays.fill(digits, biggest+1, digits.length, (short) -1); } @Override public String toString() { StringBuilder str = new StringBuilder(); for (int i=biggest; i>=0; i--){ str.append(digits[i]); } return str.toString(); } public long toLong(){ long rez = 0; for (int i=biggest; i>=0; i--){ rez = rez*10 + digits[i]; } return rez; } void setDigit(int pozition, int digit) { assert !set.get(digit) : digit + " already there " + set+" - "+Arrays.toString(digits); digits[pozition] = (short) digit; set.set(digit); } /** * @return false means state becomes inconststent * */ public boolean inc(){ int little=0; // try to inc littlest for(; little0){ // havent free digits to fill if(little > 10-set.cardinality()){ return false; }else{ // fill digits from oldest by less numbers little--; for( ;little>=0; little-- ){ setDigit(little, set.nextClearBit(0)); } return true; } } else { return true; } }// newVal=10 go ahead to next little } return false; } }

using System; using System.Collections.Generic; using System.Text; namespace ConsoleApplication1 { class Program { static void Main(string[] args) { //System.Console.WriteLine(1 reserved = new List(); ICollection ketqua = new List(); void print() { foreach (int i in ketqua) { System.Console.Write(i + " "); } System.Console.WriteLine(); System.Console.WriteLine(count); System.Console.ReadKey(); } void dequi(int next) { for (int j = 0; j < 10; j++) { int temp = next * 10 + j; if (!reserved.Contains(j) && temp < max && temp != 0) { ketqua.Add(temp); count++; reserved.Add(j); dequi(temp); reserved.Remove(j); } } } } }

Slight improvement after a couple of optimizations, including seeding (when max big enough) the biggest jump with a very conservative (max/100)-1. Code is still ugly and I will just post the timings: The one you requested: For a max of: 10,000 done in 0 ms Total Displayed: 5,274 Biggest Jump: 124 Biggest Jump begin: 9,877 Biggest Jump end : 10,000 Huge Crazy Bob's one...: For a max of: 10,000,000,000 done in 383 ms Total Displayed: 8,877,690 Biggest Jump: 123,456,790 Biggest Jump begin: 9,876,543,211 Biggest Jump end : 10,000,000,000 Have Fun,

Simple Haskell version: import Data.List(nub) main = print $ counter 10000 counter n = (length ns, maximum $ zipWith (-) (tail ns) ns) where ns = filter (not . anySame . show) [1..n] anySame xs = xs /= nub xs

@Paulo: Both 9,876,543,211 and 10,000,000,000 contain dups.

@Bob Lee Of course they are! They are the first and last element of the range, since I am presenting the jump as a closed boundary interval. Now, if I can get my implementation as clean as yours... Have fun,

Another Scala version (completely untested): def printNonRep(min: Int)(max: Int) = { (min until max).toList.flatMap { num => val str = num.toString.toCharArray val (_, res, _) = ( str :\ (false, Nil, Set[Char]()) ) { (tuple, ch) => val (dup, res, set) = tuple if (dup || set contains ch) { (true, res, set) } else { (false, ch :: res, set + ch) } } (0 /: res) { (_ * 10) + _ } } } No-where near as elegant as the first version given, but I think it works and is reasonably efficient. Of course, it's functional soup... There's probably an issue with type inference in the foldRight tuple, but I haven't tried it to be sure.

Bob Lee's version in Java is by far the best one I've seen.

@Sam Yes, it is cleeeaaan! I wonder if I am getting any meaningful performance gain over Bob's version and still can't get clean code with my strategy.

www.lolcode.com/home I will followup soon with a kickass LOLCODE implementation soon ;-)

I have written a slightly more general solution in OCaml (it can count efficiently in any arbitrary base, not only in base 10, so e.g. base 1000 is no problem for it, unlike most solutions above). It is a bit faster than Bob Lee's Java version on my box (AMD Athlon 64 X2 6000+). My program runs in 640ms, the Java implementation counts to 10^10 in ~680ms (total exec time ~750ms including JVM startup time, etc.). It can be found at eigenclass.org/hiki/ordered_permutations

What, no Lisp submissions?!

Well, here is one. (defun collect-numbers-without-repetition (min max)   (flet ((repeatedp (n)            (let ((digits (format nil "~d" n)))             (/= (length digits) (length (remove-duplicates digits))))))     (loop for i from min to max unless (repeatedp i) collect i)))

Since Mauricio upped the ante, here's a slightly longer version which runs in 210ms for max=10^10 on my machine: crazybob.org/FastBeustSequence.java.html Like Mauricio's OCaml solution, iteration of the digit set is now O(size) as opposed to O(capacity), but unlike the OCaml solution, set ops are O(1) instead of O(log(n)).

I have a different approach which works quite quickly but is highly customized to fit max=10,000. It would in its current state involve code changes if max changed. Anyway, for what its worth, the code can be found here: ragstorooks.wordpress.com/2008/07/03/cedrics-coding-challenge/

@Bob Interesting code! You have to tell us what Java version + hardware you are using. My 10,000,000,000 done in 383 ms was ran in Java 6 on under OS X on a MacPro 2008 2.8GHz. (8 cores but that is not important.) Java 5 runs it twice as slow! Tkx,

Here is a brute force implementation in Fan. class Nonrepeat { static const Int START := 0 static const Int MAX := 10000 static Void main() { Int m := 0 //max gap Int k := 0 //valid value count Int p := START //previous valid value (START..MAX).each |Int x| { Str s := x.toStr if(s.size == uniqueCharCount(s)) { k++ Int g := (x-p) echo( "$x gap: $g (count $k)") if(g>m) { m=g } p=x } } echo("Max gap is $m" ) } static Int uniqueCharCount(Str s) { u := Int[,] s.each |Int c | { if(!u.contains(c)) { u.add(c) } } return u.size } }

I still have to run it on my usual hardware to see how much faster it is, but this is for sure faster and leaner than my previous solution: public class BeustFastSequenceFinder {     private static final long LAST_NOREPS   = 9876543210L;     private static final long[] POW10;     static {         POW10 = new long[11];         long xPow = 1;         for (int i = 0; i < POW10.length; ++i) {             POW10[i] =  xPow;             xPow     *= 10;         }     }     private final long m_maxValue;     private long m_maxJumpDelta;     private long m_maxJumpPreviousPrintedValue;     private long m_printCount;     private long m_lastPrintedValue;     public BeustFastSequenceFinder(final long maxValue) {         if (maxValue <= 0)             throw new IllegalArgumentException("must be: maxValue > 0");         m_maxValue = maxValue;     }     public long getMaxJumpBegin() {         return m_maxJumpPreviousPrintedValue+1;     }     public long getMaxJumpSize() {         return m_maxJumpDelta-1;     }     public long getMaxValue() {         return m_maxValue;     }     public long getPrintCount() {         return m_printCount;     }     public void findNumbers() {         m_maxJumpDelta = Math.max(1, m_maxValue / 100);         m_maxJumpPreviousPrintedValue = 0;         m_lastPrintedValue = 0;         m_printCount = 0;         loopNext(0, (m_maxValue > LAST_NOREPS) ? LAST_NOREPS : m_maxValue, 10, 0);         final long xDelta = (m_maxValue+1) - m_lastPrintedValue;         if (xDelta > m_maxJumpDelta) {             m_maxJumpPreviousPrintedValue = m_lastPrintedValue;             m_maxJumpDelta = xDelta;         }     }     public long getMaxJumpEnd() {         return m_maxJumpPreviousPrintedValue + m_maxJumpDelta - 1;     }     protected void print(final long value) {         if (0 != value) {             final long xDelta = value - m_lastPrintedValue;             if (xDelta > m_maxJumpDelta) {                 m_maxJumpPreviousPrintedValue = m_lastPrintedValue;                 m_maxJumpDelta = xDelta;             }             m_lastPrintedValue = value;             ++m_printCount;             // System.out.println(value);         }     }     private long loopNext(long nextValue, final long maxValue, final int digitIndex, final int leftmostMask) {         if (0 == digitIndex) {             int xUsedMask = leftmostMask;             for (int i = 0; (i < 10) && (nextValue <= maxValue); ++i, ++nextValue, xUsedMask >>= 1)                 if (0 == (xUsedMask & 1))                     print(nextValue);             return nextValue;         }         else {             if (0 == leftmostMask) {                 nextValue = loopNext(nextValue, maxValue, digitIndex - 1, 0);                 for (int i = 1; i < 10; i++) {                     nextValue = loopNext(nextValue, maxValue, digitIndex - 1, (1 << i));                     if (nextValue > maxValue)                         return nextValue;                 }             }             else {                 final long xDigitPow10 = POW10[digitIndex];                 int xUsedMask = leftmostMask;                 for (int i = 0; i < 10; i++, xUsedMask >>= 1) {                     if (0 != (xUsedMask & 1)) {                         nextValue += xDigitPow10;                         if (nextValue > maxValue)                             return nextValue;                     }                     else {                         nextValue = loopNext(nextValue, maxValue, digitIndex - 1, leftmostMask | (1 << i));                         if (nextValue > maxValue)                             return nextValue;                     }                 }             }             return nextValue;         }     } } // Have Fun!

import itertools MAX=10000 # Using lists nums = filter(lambda x: len(str(x)) == len(set(d for d in str(x))), range(1, MAX+1)) print "LIST", nums print "MAX", max(map(lambda x,y: (x-y, y, x), nums[1:], nums[:-1])) print "COUNT", len(nums) # With iterators and functional programming # Remove initial dots def mkseq(max): ....return itertools.ifilter(lambda x: len(str(x))==len(set(d for d in str(x))), xrange(1, max+1)) def mkdiff(max): ....curr, next = itertools.tee(mkseq(max)) ....next.next() ....return itertools.imap(lambda x,y: (x-y, y, x), next, curr) def max_count_step(x,y): ....max_, count_ = x ....return (max(max_, y), count_+1) print "MAX, COUNT=", reduce(max_count_step, mkdiff(MAX), ((0, 0, 0), 1)) # Results: MAX, COUNT=((105, 8796, 8901), 5274)

Python: [x for x in xrange(10000) if len(str(x))==len(set(str(x)))]

@Paulo: Same as above, 3ghz Mac Pro, Java 6 w/ -server.

@Bob I tested your (very interesting) algorithm at my laptop. Yours is faster. Takes roughly 60% of mine's time for the 10 Giga test. However, it is missing the last Gap/Jump, because the last gap does not end at the max value boundary and you only collect the gap/jump data when you "print". Therefore I got results like this (both printed my way): *** Bob Lee's: *** The largest power of 10...: For a max of: 10,000,000 done in 34 ms Total Displayed: 712,890 Biggest Jump: 104,691 Biggest Jump begin: 1,098,766 Biggest Jump end : 1,203,455 *** Paulo's: *** The largest power of 10...: For a max of: 10,000,000 done in 39 ms Total Displayed: 712,890 Biggest Jump: 123,457 Biggest Jump begin: 9,876,544 Biggest Jump end : 10,000,000 So, you are just missing a final gap check to get the last and bigger one. Have fun, PJG

@PJG That last jump isn't really. There are no more jumps because after that last begin it always has duplicate digits.

I interpreted the biggest jump as being between two valid values (which 10^6 is not), but I suppose you could interpret it either way.

Ruby one-liner (not counting the import): require 'enumerator' puts (a=(1..10000).to_a.reject{|x| x.to_s.split(//).uniq!}), a.enum_cons(2).to_a.sort_by{|(b,c)|c-b}.last.inspect, a.inject(0){|s,n|s+n}

In Python u = [x for x in range(1,10000) if len(str(x))==len(set(str(x)))] gaps = [u[i+1]-u[i] for i in range(len(u)-1)] print 'number: ',len(nonrepeating) # 5274 print 'biggest gap: ',max(gaps) # 105

# solution in Ursala #import nat func = ^(nleq$^+ difference*typ,length)+ ~&triK2tkZ2FlS+ iota+successor; * ^lrhPX/~& %nP answer = func 10000

Yes, reading the original post it really looks open to both interpretations. Anyway, changing Bob's code to my interpretation is trivial and, obviously, has no impact on its to performance. I can't imagine a more efficient solution (even if a couple of details could be added(*)). (*) - Like always limiting the search to max <= 9876543210, since afterwards all numbers are repeated for base 10. But its number of digits limit does something like that too. Have Fun,

lisp (let ((seq (loop for i from 1 to 1000 when (= (parse-integer (remove-duplicates (write-to-string i))) i) collect i))) (list (length seq) (reduce #'max (maplist #'(lambda (x) (if (cdr x) (- (cadr x) (car x)) 0)) seq))))

//a recursion one , use C #include #define N 10 int flag[N]; int number[N]; int lastNumber[N]; int maxdepth; int max=0; int this_num,last_num=20000000; int run=1; int count=0; int max_begin, max_end; //set your max value here; int input_max=10000; int recu(int depth) { int i; if(depth==maxdepth) { this_num=0; //get the value of current number for(i=0;iinput_max) { run=0; return; } //update max if(max<this_num-last_num) { max=this_num-last_num; max_begin=last_num; max_end=this_num; } //store the last_num; last_num=this_num; //increase the counter by 1 count++; } else { //recursion to find the number for(i=0;i<10 && run==1;i++) { if(!(depth==0 && i==0)) { if(flag[i]==0) { //set flag number[depth]=i; flag[i]=1; //recursion recu(depth+1); //reset flag number[depth]=0; flag[i]=0; } } } } } int main() { int i; //set all flag to 0 for(i=0;i<N;i++) flag[i]=0; //start search for the number, maxdepth is actually the width of the number, i.e 45321, maxdepth = 5+1, or 564321, maxdepth=6+1 for(maxdepth=1;run==1;maxdepth++) { recu(0); } printf("max:%d\n", max); printf("begin, end: %d , %d\n", max_begin, max_end); printf("count:%d\n", count); return 0; }

//sorry for last post, the html tag covered some of the code, and that code is not complete //the following code is complete //a recursion one, using C #include #define N 10 int flag[N]; int number[N]; int lastNumber[N]; int maxdepth; int max=0; int this_num,last_num=20000000; int run=1; int count=0; int max_begin, max_end; //set your max value here; int input_max=10000; int recu(int depth) { int i; if(depth==maxdepth) { this_num=0; //get the value of current number for(i=0;i<maxdepth;i++) { this_num=(this_num<<1)+(this_num<<3)+number[i]; } //if larger than max, just abort if(input_max<this_num) { run=0; return; } //update max if(max<this_num-last_num) { max=this_num-last_num; max_begin=last_num; max_end=this_num; } //store the last_num; last_num=this_num; //increase the counter by 1 count++; } else { //recursion to find the number for(i=0;i<10 && run==1;i++) { if(!(depth==0 && i==0)) { if(flag[i]==0) { //set flag number[depth]=i; flag[i]=1; //recursion recu(depth+1); //reset flag number[depth]=0; flag[i]=0; } } } } } int main() { int i; //set all flag to 0 for(i=0;i<N;i++) flag[i]=0; //start search for the number, maxdepth is actually the width of the number, i.e 45321, maxdepth = 5+1, or 564321, maxdepth=6+1 for(maxdepth=1;run==1;maxdepth++) { recu(0); } printf("max:%d\n", max); printf("begin, end: %d , %d\n", max_begin, max_end); printf("count:%d\n", count); return 0; }

@Bob: interesting representation of the set of remaining digits. I have nothing against imperative code in general (I use it often in OCaml), but I decided to see how far a functional set could go. The resulting program takes three additional lines of code and here's how it compares to your FastBeustSequence on an AMD Athlon 64 X2 6000+ (using Java 6): $ time ./beust Found 8877690 numbers under 10000000000. Max jump: 104691357 (1098765432 -- 1203456789). real 0m0.273s user 0m0.268s sys 0m0.004s $ time java -server TestBeustSequence 10000000000 count: 8877690 largest gap: 104691357 (1098765432..1203456789) 269ms real 0m0.350s user 0m0.328s sys 0m0.008s The difference is within the experimental error; I guess it's a draw :) You can find the code at eigenclass.org/misc/beust.ml The set of digits is represented with two lists (in a way reminiscent of a functional queue), and all the operations are (amortized) O(1) and non-destructive.

simpler ruby to to the basic stuff (10..12).to_a.reject { |x| x.to_s.split(//).uniq! }

I found that challenge very interesting. I have an idea about finding the largest gap between two unvalid numbers. I tried that way: I think that a very simple alorithm can generate all valid numbers (ie with no pair of symbols) simply in making the current one grow by the right. I mean: 10,12,13,14,15,16,17,18,19,20,21,23,24, etc. We are to jump a gab when the unit just preceeds a symbol already used. So, the more the numbers used are near each other, the more the gab may be big. I mean: 4563 will goes to 4567 (gap of 4), but 4573 goes to 4576 (gap of 3). I think this is the way gap appears. So I tried to find a good combination, and I immediately found: 9876 which jumps over 9877, 9878, 9879, 988X, 989X, then 99XX, until 10234 (gap = 358). Ok, gap seems cool, but makes us go too far (over 10000). Trying that method with 3 symbols gives: 987 goes to 1023 with a gap of 36. I have a good feeling about that. Sorry for my English, and for the lack of programming example. Thanks. Mathieu BORDAS, France

Prolog Version(Well, GNU Prolog) checkit([]):-!. checkit([H|T]):- \+memberchk(H,T),checkit(T). dif([_|[]],[]). dif([X,Y|T],R):-dif([Y|T],T2), D is Y-X, append([D],T2,R),!. beust(Low,Hi):- retractall(norpt(_)), for(C,Low,Hi), write_term_to_codes(X,C,[]), checkit(X), assertz(norpt(C)), fail. beust(_,_):-!. printResults:- bagof(X,norpt(X),R), !, length(R,Len), dif(R,D), max_list(D,M), write('Count : '),write(Len),nl, write('Max difference : '),write(M),nl, write('Results '),write(R),nl. printResults:-!. main:- beust(98,120),printResults.

Here's one in awk. function scan(num) { nlen = length(num); for (j = 1; j <= nlen; j++) { cmp = substr(num, j, 1); for (i = j; i < nlen; i++) if (index(substr(num, i+1, nlen-j+1), cmp)) return 0; } return 1; } function iter(max) { for (n=1; n<=max; n++) if(scan(n)) print n; } BEGIN { iter(5440) }

@Mauricio: When I try to run your program, I get: File "beust.ml", line 19, characters 12-26: Integer literal exceeds the range of representable integers of type int

I modified my test program to not allocate objects. Now it runs in 150ms for 10^10: crazybob.org/FastBeustSequence.java.html crazybob.org/TestFastBeustSequence.java.html

Bob: you need a 64-bit ocamlopt. I pushed the functional set some more. eigenclass.org/misc/beust2.ml Best of 5 runs: $ time ./beust2 Found 8877690 numbers. Max jump: 104691357 (1098765432 -- 1203456789). real 0m0.217s user 0m0.216s sys 0m0.000s $ time java -server TestFastBeustSequence 10000000000 count: 8877690 largest gap: 104691357 (1098765432..1203456789) 207ms real 0m0.309s user 0m0.256s sys 0m0.020s The standard deviation is quite large, around 15ms (real time for OCaml, System.nanoTime deltas for Java; a bit more for the latter) or so... I guess an imperative structure is required for further improvements, but it's too late.

Best of 5 runs on my computer: eigenclass.org/misc/beust2.ml: $ time ./beust2 Found 8877690 numbers. Max jump: 104691357 (-1048718216 -- -944026859). real 0m0.237s user 0m0.233s sys 0m0.004s crazybob.org/FastBeustSequence.java.html: $ time java TestFastBeustSequence 10000000000 count: 8877690 largest gap: 104691357 (1098765432..1203456789) 150ms real 0m0.272s user 0m0.233s sys 0m0.042s So, not counting Java startup overhead, we're looking at 237ms (OCaml) vs 150ms (Java).

Interesting to see the effects of -client and -server on the Java versions. With -client (and Soylatte 1.0.2 on a MacBook Pro 2.16Ghz Core Duo) this one is faster than FastBeustSequence (though not as elegant): slm888.com/snippets/Beust.java slm888.com/snippets/BeustTest.java $ java -client BeustTest 10 count: 8877690 max gap: 104691357 (1098765432..1203456789) 352ms $ java -client TestFastBeustSequence 10000000000 count: 8877690 largest gap: 104691357 (1098765432..1203456789) 456ms With -server they both have best run times of around 400ms.

The best times I can get after N (= a few dozen) runs are 205ms for Java (without startup overhead), 212ms for OCaml with the functional set. While my box runs the OCaml code a bit faster, yours is much better at Java. I'm using this JVM: java version "1.6.0_04" Java(TM) SE Runtime Environment (build 1.6.0_04-b12) Java HotSpot(TM) 64-Bit Server VM (build 10.0-b19, mixed mode) I've compiled the OCaml program in a 32-bit jail with no substantial difference in speed (it is meant to be compiled with a 64-bit ocamlopt though; you can notice the integer overflow in the output you're getting). Either we're observing a AMD vs. Intel discrepancy, or the 32-bit JVM is much faster than the 64-bit one (even though 32-bit OCaml isn't really faster than 64-bit, on my machine). Not that it matters.

I have ported that fast Java code to C, it's about twice faster on my PC: codepad.org/wlz2Vaqn

A nicer Perl version: #!/usr/bin/perl use strict; use warnings; use List::Util qw(max); use List::MoreUtils qw(pairwise); my @num = grep { !/(.).*\1/ } 1 .. 10_000; my $max_diff = max pairwise { $b - $a } ( $num[ 0 .. $#num - 1 ], $num[ 1 .. $#num ], ); print @num . "numbers, max diff $maxdiff\n"; print "@num\n";

Hi, my code is very simple but are not getting through properly via this comment, Contact me via email if you are interested. /* * Author : Unni Prasad * Email : unniready@gmail.com * Date : July 07,2008 */ public class Counter { public static void main(String [] args) { int limit=10000; int count=0,flag=0,number,jump=0,max_jump=0,max_jump_position=1; int i,j,k,l; int array[]=new int[5]; int answer[]=new int[10000]; for(i=0;i2) jump=answer[count-1]-answer[count-2]; if(max_jump<jump){ max_jump=jump; max_jump_position=count-1; } } } System.out.println("The biggest jump was from "+answer[max_jump_position-1]+" to " +answer[max_jump_position]); System.out.println("The max jump was : "+max_jump); System.out.println("Total number counted : "+count); } } /*Output The biggest jump was from 1098 to 1203 The max jump was : 105 Total number counted : 5275 */

Hi, My codes are not getting through this comment, if you are interest contact me via email /* * Author : Unni Prasad * Email : unniready@gmail.com * Date : July 07,2008 */ public class Counter { public static void main(String [] args) { int limit=10000; int count=0,flag=0,number,jump=0,max_jump=0,max_jump_position=1; int i,j,k,l; int array[]=new int[5]; int answer[]=new int[10000]; for(i=0;i2) jump=answer[count-1]-answer[count-2]; if(max_jump<jump){ max_jump=jump; max_jump_position=count-1; } } } System.out.println("The biggest jump was from "+answer[max_jump_position-1]+" to " +answer[max_jump_position]); System.out.println("The max jump was : "+max_jump); System.out.println("Total number counted : "+count); } } /*Output The biggest jump was from 1098 to 1203 The max jump was : 105 Total number counted : 5275 */

Final couple of tweaks to mine: slm888.com/snippets/Beust.java slm888.com/snippets/BeustTest.java It now accepts a radix so you can try a larger range of values, eg base 11: $ java BeustTest 10000000000 11 count: 62353010 max jump: 104690246 (10a9876543..1203456789) 1858ms

@Bob The new method names for the Digit class are a readability improvement too - especially since your implementation is quite original / unusual. @Mark The radix thing is not so usefull since the maximum value without repeated digits is: 9876543210. Above this value ALL integer numbers have repeated digits. Have Fun,

@Paolo That's correct for base 10 numbers, but I'm applying the radix to the calculation as well, so in base 11, a9876543210 is the maximum value without repeating digits. There are limits though. Eg. in hex, fedcba987654321 is the maximum non-repeating value it's capable of finding since the data types I'm using limit it to values less than 2^63.

@Paulo Oops, sorry I mis-typed your name on that last comment.

@Mark Mahieu Sorry, I had missed the multi-base "detail". And don't hurry: that mistyping is quite common. =;o)

var nums = (from n in Enumerable.Range(1, 10000) where n.ToString().Select(c => c).Distinct().Count() == n.ToString().Length select n).ToArray(); var gap = -1; for (int n = 1; n < nums.Length; n++) gap = Math.Max(gap, nums[n] - nums[n - 1]); Response.Write(String.Format("count: {0}, max gap: {1}", nums.Length, gap)); Takes about 0.01sec on my old 3.2GHz Athlon. And since it is written in performant C# I don't have to jump through hoops to optimize it.

@Wheelwright "Takes about 0.01sec on my old 3.2GHz Athlon. And since it is written in performant C# I don't have to jump through hoops to optimize it." haha that's not very impressive really, it's barely faster than the Ruby one-liner... Try to count up to 10000000000 with that code. See you in a couple days ;-) (if you can stand the disk trashing)

public class Puzzle { public static void main(String []args) { int max=new Integer(args[0]).intValue(); String digitString=null; //holds string representation of numbers. boolean flag; for(int i=1;i<=max;i++) { flag=true; digitString=new Integer(i).toString(); //start of code for comparing digits of a number with each other for(int strcount=0;strcount<digitString.length()-1;strcount++) { if(digitString.substring(strcount,strcount+1).equalsIgnoreCase(digitString.substring(strcount+1,strcount+2))) { flag=false; } else{ flag=true; break; } } //end of code for comparing digits of a number with each other if(flag==true) { System.out.println(i); } } } }

Sorry Cedric...The code in my previous comment is wrong and incomplete.I had posted the modifed code in my blog (ananyobanerjee.blogspot.com).Please have a look.

I put a Common Lisp version here: paste.lisp.org/display/63602 It does the 10,000 solution in 0.005 seconds.

No solution using * bash * vi (remember vi is turing complete!)

A 'lispier' lisp solution (no iteration, just tail recursion) which also runs faster than any of my iterative solutions interestingly paste.lisp.org/display/64850

class Beust {     public static void Run(int max)     {         System.Diagnostics.Debug.Assert(max > 1);         int maxGap = 0;         int last = 0;         int total = 0;         for (int i = 1; i <= max; ++i)         {             if (DoDigitsRepeat(i) == true)                 continue;                          Console.Write("{0}, ", i);             ++total;             int gap = i - last;             maxGap = Math.Max(gap, maxGap);             last = i;         }         Console.WriteLine("\nTotal: {0}", total);         Console.WriteLine("Max Gap: {0}", maxGap);     }     private static bool DoDigitsRepeat(int num)     {         //Used to track which digits have already been encountered         int table = 0;         while (num > 0)         {             int digit = num % 10;             num = num / 10;             int index = 1 << digit;             if ((table & index) == index){                 return true;             }             else{                 table |= index;             }         }         return false;     } }

//javascript version (apply in c/c++,java,c#) //using firebug over FF: function check(x) { var x=x+''; var z= 0 for( y in x) { if( z & (1<<x[y])) return false z |= (1<<x[y]); } return true; } for( var n =0 ;n<1000; n++) if( check(n)) console.log(n)

#!PYTHON max = 10000 # Dual-brute-force, First attempt ---------- nums = [x for x in range(1,max+1) if len(list(str(x))) == len(set(str(x)))] count = len(nums) gaps = [(nums[i]-nums[i-1],i) for i in range(1,count)] gaps.sort() print nums print count i = gaps.pop()[1] print 'GAP:',nums[i-1],'->',nums[i] #---- Refactored for effeciency. count = last = 0 gap = (1,1) nums = [] for x in range(1,max+1): if len(list(str(x))) == len(set(str(x))): nums.append(x) count += 1 if last and x - last > gap[1] - gap[0]: gap = (last,x) last = x print nums print "\nCOUNTED:", count print "GAP :", gap

So I'll ask the obvious question: do leading zeroes count as repeated digits? (Is that an African or a European swallow?)

This is by no means the fastest way, but is done using list generators only #!/usr/bin/env python maximum = 10000 numbers = [a for a in range(1,maximum+1) if len(set(str(a))) == len(str(a))] biggest_jump = max([numbers[i] - numbers[i-1] for i in range(1, len(numbers))]) print len(numbers), biggest_jump you can also work out biggest_jump using zip biggest_jump = max([b-a for a,b in zip(numbers, numbers[1:])])

ghci> let xs = filter (\x -> let st = show x in st == nub st) [1..10000] ghci> length xs 5274 ghci> maximum . map (abs . uncurry (-)) . zip xs . tail $ xs 105

I don't understand exactly the definition of the problem. What does brute-force mean? Linear respect to max? I am pretty lazy to write the code. My high level solution is the following, which is NlogN complexity, where N = number of digits of _max_, power 10. Actually it requires to subclass the standard library function of the binary tree, as as far as I know, there is no function in C/Java/Ruby to extract the left/right leaves of the tree. tot_digits = number of digits of _max_ create an empty ordered binary tree max_difference = 0 for all the permutations from 1 to 10^tot_digits: if permutation <= _max_ put in the tree and extract left and right if there is left and the difference with permutation is greater than max_difference, store else if there is right and the difference with permutation is greater than max_difference, store total_permutations = size of the tree

# a single line lambda, returns numbers in which no digit repeats itself cunique = lambda x, y: [i for i in range(x,y) if len(set(str(i)))==len(str(i))] print cunique(1, 10000)

Here's a simple, permutation-based Haskell solution: Prelude> let perms 0 _ = [[]]; perms n xs = concat [ map (y:) (perms (n-1) (filter (/=y) xs)) | y <- xs] Prelude> let numbers = filter ((/='0').head) $ concatMap (flip perms ['0'..'9']) [1..] Prelude> take 100 numbers ["1","2","3","4","5","6","7","8","9","10","12","13","14","15","16","17","18","19","20","21","23","24","25", "26","27","28","29","30","31","32","34","35","36","37","38","39","40","41","42","43","45","46","47","48","49","50", "51","52","53","54","56","57","58","59","60","61","62","63","64","65","67","68","69","70","71","72","73","74","75", "76","78","79","80","81","82","83","84","85","86","87","89","90","91","92","93","94","95","96","97","98", "102","103","104","105","106","107","108","109","120","123"] (Sorry if somebody posted something like this already, and I missed it).

Here's my dumb haskell solution: import Data.List (nub) nodup n = (sn == nub sn) where sn = show n beust = filter nodup [1..10000] main = do print $ maximum $ zipWith (-) (tail beust) beust print (length beust)

Bob's solution in C# - 459 ms.

k4:{(|/-':;#:)@\:&(=').#:''(::;=:')@\:$1+!x} 10.1 ms for 10,000, 141 ms for 100,000, 160 ms for 1,000,000

Oops, that should have been 1560 ms for 1,000,000

hmmmmmmmmmmmmmmmmm, It seems that SQL is not cool because no one has tried to solve this problem with SQL. Here Oracle SQL: select num, count_tot, (max(diff) over ()) max_diff from ( select num , (count(*) over ()) count_tot , (num-(lag(num) over (order by num))) diff from ( select level num from dual connect by level = length(num) -1 and length(replace(translate(num,'1','X'),'X',null)) >= length(num) -1 and length(replace(translate(num,'2','X'),'X',null)) >= length(num) -1 and length(replace(translate(num,'3','X'),'X',null)) >= length(num) -1 and length(replace(translate(num,'4','X'),'X',null)) >= length(num) -1 and length(replace(translate(num,'5','X'),'X',null)) >= length(num) -1 and length(replace(translate(num,'6','X'),'X',null)) >= length(num) -1 and length(replace(translate(num,'7','X'),'X',null)) >= length(num) -1 and length(replace(translate(num,'8','X'),'X',null)) >= length(num) -1 and length(replace(translate(num,'9','X'),'X',null)) >= length(num) -1) or (length(num)=1) ) order by num / NUM COUNT_TOT MAX_DIFF ---------- ---------- ---------- 1 738 11 2 738 11 3 738 11 4 738 11 5 738 11 6 738 11 7 738 11 8 738 11 9 738 11 10 738 11 12 738 11 13 738 11 ..... 967 738 11 968 738 11 970 738 11 971 738 11 972 738 11 973 738 11 974 738 11 975 738 11 976 738 11 978 738 11 980 738 11 981 738 11 982 738 11 983 738 11 984 738 11 985 738 11 986 738 11 987 738 11 I used the Mikito way the generate the numbers. If anyone knows how to use a regular expression as a filter to check for duplicate digits I could use this regular expressions instead of all the translate functions?

My sql statement becomes maimed, I can't post it properly. Beneath the connect by level.... one should insert: ) where (length(replace(translate(num,'0','X'),'X',null)) >= length(num) -1

This one's pretty easy. is_unique_digital(X) -> Base = int_to_list(X), Uniqued = lists:usort(Base), length(Base) = length(Uniqued). non_repeating_digit_numbers_in(Low, High) -> [ X || X <- lists:seq(Low,High), is_unique_digital(X) ].

#!perl -wl use strict; my $max=10000; my @nums; my$count=1; my $max_jump=1; my $numbers=0; while($count $max_jump; } } $count++; } print join (" ",@nums); print "\n $numbers , jump $max_jump";

there is some problem i am not able to post my code

A tacit solution in J: ddr=: (#~ [: (= ~.&.>) 10&#.^:_1&.>)@: i.

I didn't originally see all the requirements. Drawing on Danil's code to improve my own, here's a complete solution: summarizeTo=: (bigjump, #) & cf bigjump=: [: >./ 2-~/\] cf =: ddr @: >: @: i. ddr=: #~ ([:*./ [:~: 10&#.^:_1)"0 summarizeTo 1000 11 738

My Haskell solution is not as fast as some of the other optimized solutions here, nor as elegant as some of the unoptimized proposals, but it demonstrates memoization, recursive values and two ways to force strict evaluation. Compiled, it runs the whole list in about 2 seconds. module Main where import Data.List(foldl') import Data.Bits data Result = Result !Int !Int !Int deriving Show beust :: [(Int, Int)] beust = tail digits ++ [(num * 10 + n, ds') | (num, ds) <- beust, (n, d) <- digits, let ds' = ds .|. d, ds' /= ds] digits = [(n, bit n) | n <- [0..9]] calc m = foldl' step (Result 0 0 0) . takeWhile (<= m) . map fst $ beust where step (Result maxJump count prev) n = Result (max maxJump (n - prev)) (count + 1) n main = do let (Result maxJump count _) = calc (9876543210) putStrLn $ "max jump: " ++ show maxJump putStrLn $ "count: " ++ show count Further optimization suggestions welcome.

3 lines of F# let result = [0 .. 10000] |> List.filter (fun x -> x.ToString().ToCharArray() |> (fun (arr : _[]) -> arr.Length = (Set.ofArray arr).Count)) let max = List.max result let gap = Seq.pairwise result |> Seq.map (fun (a,b) -> b-a) |> Seq.max

I'll publish this with more info in my blog @ madurax86.co.nr well lets get down to business! I coded it in C and ran it on Ubuntu 9.10 system it tells that it took only 0.010 seconds to execute! Well my approach was different I didn't convert the integers to string, I just let it be integers and did all comparing without any type conversion. Here's the code. #include #include #include clock_t startm, stopm; #define START if ( (startm = clock()) == -1) {printf("Error calling clock");exit(1);} #define STOP if ( (stopm = clock()) == -1) {printf("Error calling clock");exit(1);} #define PRINTTIME printf( "\nExecution Time : %6.3f seconds.", ((double)stopm-startm)/CLOCKS_PER_SEC); #define MAX 10000 #define t 5 int main(){ int i,j=1,k=10,l,n,x,y,z,prev=0,jmp=0,bTop=0,bLow=0; START; for (i=10;i<MAX;i++){// drop 1 to 10 and count to MAX if (i==k){ // keep track of number length k=k*10; j++; // j= number length } y=i; int a[t]; // list to keep the digits of the number for (l=0;l<j;l++){// go through the digit list x=y%10; // get digit list by simple math, x gets the digit this starts from the end of the number y=y/10; z=0; for (n=0;n<l;n++){ if (a[n]==x){z=1; break;}// check(1) one digit appears again } a[l]=x;// add new digit if (z==1) break;// if the check(1) found duplicates get out of loop } if (z==0){ printf("\n %d",i); x=i-prev; if (jmp<x){ jmp=x; bTop=i; bLow=prev;} prev=i; } } STOP; printf("\nBiggest jump is %d: %d to %d",bTop-bLow,bLow,bTop); PRINTTIME; }

if my assumption is not wrong about the your challenge, here's the vb6 code, what you required are textbox as text1and command button as command1,suggestion are welcome: Private Sub Command1_Click() maxjump = 0 maxjumpno = "" Counts = 0 prevnum = 0 For a = 1 To 10000 If a = 122 Then jg = gg End If valid = True For b = 1 To Len(a) twin = 0 For c = 1 To Len(a) If Mid(a, b, 1) = Mid(a, c, 1) Then twin = twin + 1 End If If twin >= 2 Then valid = False End If Next c Next b If valid = True Then Text1.Text = Text1.Text & a & "," Counts = Counts + 1 If Val(a) - prevnum >= maxjump Then maxjump = Val(a) - prevnum maxjumpno = a End If prevnum = a End If twin = 0 Next a MsgBox "max jump = " & maxjump & " Max Jump Number = " & maxjumpno & " count = " & Counts End Sub

here is my solution using java-- /** * * @author Dinesh */ public class Main { public static boolean isCorrect(int number){//this method returns true if the condition ok boolean isOK = true; String numberValues = number+""; char array[] = numberValues.toCharArray(); for(int i=0;i<array.length;i++){ for(int j=0;j<i;j++){ if(array[i]==array[j]){ isOK = false; break; } } } return isOK; } public static void main(String[] args) { int total=0; int previousValue = 0; int maxGap = 0; int max = 10000; System.out.println("The numbers are ---"); for(int i = 0;i <= max;i++){ if (isCorrect(i)) { int gap = i-previousValue; if(maxGap "+i); previousValue = i; total += i; } } System.out.println("Maximum gap is -- "+maxGap); System.out.println("The total is -- "+total); } }