Lazy Clifford

Computer Science Level 5

Clifford likes to write down sequence of positive integers. Everyday, he spend 3 hours writing from 1 1 to 1000000 1000000 on an infinite large whiteboard and then solve brilliant.org problems.

One fateful day, he woke up late and have little time left before he should log in to brilliant.org and continue his 1000000 1000000 days streak. Instead of solving a practice problem to continue his streak, he wants to take a shortcut for writing the sequence. The method is to skip every same consecutive digits that occurs in the sequence to save some time.

Your mission is to help Clifford count how many digits he should write.

Original sequence :

1234567891011121314151617181920212223... 1234567891011121314151617181920212223...

Sequence after taking shortcut :

123456789101213141516171819202123... 123456789101213141516171819202123...


The answer is 5300003.

View wiki
Christopher Boo by Christopher Boo , 24, Singapore

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

5 solutions

Brock Brown
May 20, 2015

Python 2.7: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
 
def shortcut():
    cur_digit = ''
    for n in xrange(1, 1000001):
        for digit in str(n):
            if cur_digit != digit:
                yield digit
                cur_digit = digit
count = 0
for digit in shortcut():
    count += 1
print "Answer:", count

5 Helpful 0 Interesting 0 Brilliant 0 Confused

Very nice solution. An optimization could be: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
 
def shortcut(m):
    cur_digit = ''
    tot = 0
    for n in xrange(1, m+1):
        for digit in str(n):
            if cur_digit != digit:
                tot += 1
                cur_digit = digit
    return tot

shortcut(1000000)

Abdelhamid Saadi - 6 years ago
Horisadi Afyama
May 28, 2015

;)

1 Helpful 0 Interesting 0 Brilliant 0 Confused
Arulx Z
May 15, 2015

Simplest (but least efficient) solution of which I can think of. I will work on a better solution later. 

1
2
3
 
String n = "";
for(int i = 1; i <= 1000000; i++) n += i;
System.out.println(n.replaceAll("(.)\\1{1,}", "$1").length());

1 Helpful 0 Interesting 0 Brilliant 0 Confused
Pranshu Gaba
May 12, 2015

I defined a function skip(number) that takes in an int or a string. First, it is converted to a list whose elements are digits of the argument. Then each digit is compared with its following digits. If they are same the following digit is deleted. This is repeated until next digit is different. In the end, the list is returned without any consecutive digits being repeated.

This is my code in python 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
 
# function converts string or int to a list
def skip(number):
    list = [int(x) for x in str(number)]
    i = 1
    while i < len(list):
        if list[i - 1] == lists[i]:
            del list[i]
        else:
            i = i + 1
    return list

# makes a string with numbers from 1 to 1000000
string = ''
for x in xrange(1, 1000001):
    string += (str(x))

# prints out number of digits in skip(string)
print len(skip(string))

1 Helpful 0 Interesting 0 Brilliant 0 Confused
Bill Bell
May 10, 2015

I knew I should have checked for the one-off! What I like is that brute force is actually considerably faster. Here it is, in essentially a single line using itertools .

I'd like to say 'live and learn' except that I'm way too old. ;)

Scan through the numbers from 1 through one million. Retain the last digit of the previous number. Beginning with that last digit scan through the digits of the concatenated digits of each number, casting out duplicate digits. Note the number of unduplicated digits and retaining the last digit for use on the next iteration.

1 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...