This problem is said to have appeared in Google's entrance exam.
Problem:
1
1 1
2 1
1 2 1 1
1 1 1 2 2 1
what is the next line ? [S]
Subscribe to:
Post Comments (Atom)
3 comments:
I have found this nice beautiful algorithm.For creating the n th step [n>2] , rearrange the digits in the [n-1]th step so all the one's are at the begining and two's are at the ending[If there is no 2 at the [n-1]th step then the nth step starts with 2].then, attach digits of [n-2]th step.
This is quite a famous kind of sequence.
*)Solution:
Every number in the series describes the number of countiguous blocks of a single digit in the previous number.
*)A brute force description is
1 should be treated alone
1 1 means there is 1 'one' in the previous number
2 1 means there are 2 'ones' in the previous number
1 2 1 1 means there is 1 'two' followed by 1 'one' in the previous number
1 1 1 2 2 1 means there is 1 'one' followed by 1 'two' followed by 2 'ones'
So the next number in the sequence is
3 1 2 2 1 1
An interesting extension of this problem will be to see what happens if a digit has more than 9 appreances.
In order to build lines of any specified length, we can choose a num system of a base such that ambigity does not arise.
Anyway, we may come up with various algorithms to this.
Post a Comment