CODEWITHSUNDEEP
algorithmcryptarithmetic-puzzle
Sai Kumar
Sai Kumar

Reputation: 209

is it possible to find the n'th number in this sequence using code which does not require bruteforce?

I have been asked this question where I am asked to find the Nth number in the sequence. The sequence goes like this 555 35 1315 11131115 31133115 1321232115.

The sequence is a count of each character in the string. Let's say I start with 555, then since I have three occurances of '5', the next number would be 35. Similarly, since I have one occurance of 3, and one occurance of 5, the next number would be 1315.

Now, I was asked this question where I have to get the nth number of such sequence with input being any random number. I have suggested a bruteforce approach, or if there are a fixed set of numbers, then we could cache the results. I want to know if there is a better way to code this? or is there any existing algorithm for such a problem statement?

Upvotes: 0

Views: 160

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59154

The length of the numbers in the sequence grows exponentially (unless you start with 22). According to Wikipedia, each number is about 30% longer than the last.

Because of this exponential growth, the time required to iteratively generate (brute force) and output the nth number is in O(length(input) + length(output)), except 22, and you can't get complexity less than that.

Maybe the interviewer had a problem with your specific brute force implementation.

If you were asked for the first 10 digits of the Nth number, or something like that, then there would be a more interesting answer... but I think that would be too hard for an interview.

Upvotes: 1

Related Questions