How do I write a recursive function that that takes an int value and returns the digit with the longest consecutive sequence?
For example, f(1122333) returns 3 and f(1223) returns 2
I have no idea how to approach this problem, and I'm kind of new to recursion in general.
Something like this. Not tested. Was fun to think about though.
Pseudo code:
(Assumes integer division)
Def number helperLongest(number myNum):
Return longest(myNum, -1, 0, -1, 0)
Def number longest(number myNum,number prevLongest, number numOfPrevLong, number currentLongest,number numOfLongest):
If (myNum/10 < 1) //base case
If (myNum == currentLongest)
numOfLongest++
Else //deal with corner case of < 10 input
If (numOfLongest > numOfPrevLong)
prevLongest = currentLongest
numOfPrevLongest = numOfLongest
currentLongest = myNum
numOfLongest = 1
return (numOfLongest>numOfPrevLong)?currentLongest:prevLongest
Else //recurse
if(myNum%10 == currentLongest)
numOfLongest++;
Else //have to break the chain
if (numOfLongest > numOfPrevLongest)
prevLongest = currentLongest
numOfPrevLongest = numOfLongest
currentLongest = myNum%10
numOfLongest = 1
myNewNum = myNum/10;
return longest(myNewNum,prevLongest,numOfPrevLong,currentLongest,numberOfLongest);
In words: go through the number digit by digit, starting from the end. If the current last digit matches the one before it, increment the counter. If it doesn't, and it's bigger than the previous maximum, save it. Reset the current digit to the current last digit and reset the counter. Chop off the last digit. Feed the smaller number and all of this information back into the function until you get down to one final digit (the first digit in the original number). Compare your current counter with the maximum stored, and return the larger.
One note: in case of a tie the first substring of matching numbers (which is actually the last substring in the original number) would be returned. If the other behavior is desired, then interchange the two > with >=.
The easiest thing I can think of is to do this via tail recursion. Within the function, I would have a private function that we would use for recursion. First, I would convert the integer into a list where each digit is separated as an individual element. This recursive private function takes in a list of elements, the number we are investigating, current number that holds the longest consecutive sequence and a count describing how many times we have seen. The count is important as we will be counting how many times we have encountered a particular reference number. The list is as an input is important, because we can simply provide a list with one less element for each call by skipping over the first element of this list. Eventually, we will get down to only one number in the list, which is the base case.
In other words, with any recursive algorithm, you need the base case, which is where we will stop and return something, and the recursive case where we need to call the function with the inputs modified.
The base case is when we provide a number with a single digit. This means that we've reached the end of the number. If this is the case, what we need to do is check to see if this value is equal to the current value that is currently considered to be consecutive. If this value matches, we increment current consecutive count by 1. Should this value exceed the current longest consecutive count, we will return this single digit as the number that pertains to the longest consecutive sequence. If not, then we simply return what this value was before we decided to do this check.
The recursive case is slightly more complicated. Given a digit we're looking at, we check to see if this digit is equal to the digit that is being considered as part of the consecutive stream. If it is, increment the count of this digit by 1, and we check to see if this count is larger than the current largest consecutive count. If it is, then we need to update the current longest value to this value and also update the longest count. If this doesn't match, we reset the count back to 1, as this is the first digit of its kind to be encountered. The current value to match will be this value, and we will recurse where we submit a list of values that starts from the second index onwards, with the other variables updated.
As we keep recursing and specifying values of the list from the second index onwards, we would effectively be searching linearly in the list from the beginning up until the end when we finally reach the last element of the list, and this is where we stop.
Without further ado, this is what I wrote. The function is called longest_consecutive_value and it takes in an integer:
# Function that determines the value that has the longest consecutive sequence
def longest_consecutive_value(value):
# Recursive function
def longest_recursive(list_val, current_val, current_longest_val, longest_count, count):
# Base case
if len(list_val) == 1:
# If single digit is equal to the current value in question,
# increment count
if list_val[0] == current_val:
count += 1
# If current count is longer than the longest count, return
# the single digit
if count > longest_count:
return list_val[0]
# Else, return the current longest value
else:
return current_longest_val
# Recursive case
else:
# If the left most digit is equal to the current value in question...
if list_val[0] == current_val:
# Increment count
count += 1
# If count is larger than longest count...
if count > longest_count:
# Update current longest value
current_longest_val = list_val[0]
# Update longest count
longest_count = count
# If not equal, reset counter to 1
else:
count = 1
# Current value is the left most digit
current_val = list_val[0]
# Recurse on the modified parameters
return longest_recursive(list_val[1:], current_val, current_longest_val, longest_count, count)
# Set up - Convert the integer into a list of numbers
list_num = map(int, str(value))
# Call private recursive function with initial values
return longest_recursive(list_num, list_num[0], list_num[0], 0, 0)
Here are some example cases (using IPython):
In [4]: longest_consecutive_value(1122333)
Out[4]: 3
In [5]: longest_consecutive_value(11223)
Out[5]: 1
In [6]: longest_consecutive_value(11223334444555555)
Out[6]: 5
In [7]: longest_consecutive_value(11111111122)
Out[7]: 1
In [8]: longest_consecutive_value(1122334444)
Out[8]: 4
Note that if there are multiple digits that share the same amount of consecutive numbers, only the first number that produced that length of consecutive numbers is what is output. As noted by Ron Thompson in his post, if you desire the most recent or last consecutive digit that satisfies the requirements, then use >= instead of > when checking for the counts.
