*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

Ketilon September 4, 2008 - 8:37 amHere’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).

#2 by

noneon September 5, 2008 - 11:39 pmHere’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)

#3 by

B Pon September 14, 2008 - 9:53 amBob’s solution in C# – 459 ms.

#4 by

Aaron Davieson September 22, 2008 - 6:55 pmk4:{(|/-‘:;#:)@\:&(=’).#:”(::;=:’)@\:$1+!x}

10.1 ms for 10,000, 141 ms for 100,000, 160 ms for 1,000,000

#5 by

Aaron Davieson September 22, 2008 - 6:57 pmOops, that should have been 1560 ms for 1,000,000

#6 by

RCon October 5, 2008 - 6:47 amhmmmmmmmmmmmmmmmmm,

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?

#7 by

RCon October 5, 2008 - 7:03 amMy 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

#8 by

John Haugelandon December 8, 2008 - 1:57 pmThis 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) ].

#9 by

vidhuton February 27, 2009 - 6:52 am#!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”;

#10 by

vidhuton February 27, 2009 - 6:55 amthere is some problem i am not able to post my code

#11 by

Tracy Harmson May 28, 2009 - 5:58 pmA tacit solution in J:

ddr=: (#~ [: (= ~.&.>) 10&#.^:_1&.>)@: i.

#12 by

Tracy Harmson May 29, 2009 - 9:02 amI 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

#13 by

Peter Markson May 30, 2009 - 7:20 pmMy 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.

#14 by

F. Levineon December 4, 2009 - 7:45 pm3 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

#15 by

Maduraon January 13, 2010 - 12:25 amI’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;

}

#16 by

The Don January 4, 2011 - 7:05 pmif 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

#17 by

Dineshon March 13, 2011 - 6:49 amhere 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);

}

}