This is a complex sounding problem that is actually very simple, and yet requires some creativity to solve.
Let's consider an array, with elements being boolean (True if the number of loaves with the person in that index in the line is even, else False). A typical starting array may look like this:
TTTTF
Now this case is interesting. We observe that in order to eliminate F entirely, we must have a situation with two nieghboring F's. Then we can give one loaf to both, and convert them to T. Hence, the total number of F's must be even, otherwise a solution is not possible, in which case we return "NO".
Now let's look at some examples cases where it is possible:
1. TFTFT
2. TTFFT
3. FTTTF
I tried some experimentation, and came up with this algorithm to distribute the loaves:
Let's consider an array, with elements being boolean (True if the number of loaves with the person in that index in the line is even, else False). A typical starting array may look like this:
TTTTF
Now this case is interesting. We observe that in order to eliminate F entirely, we must have a situation with two nieghboring F's. Then we can give one loaf to both, and convert them to T. Hence, the total number of F's must be even, otherwise a solution is not possible, in which case we return "NO".
Now let's look at some examples cases where it is possible:
1. TFTFT
2. TTFFT
3. FTTTF
I tried some experimentation, and came up with this algorithm to distribute the loaves:
- Loop through every element. If that element is T, move on.
- If that element is F, then invert that element and the element to its right. Increment a "breadCount" variable by 2 everytime we do this.
- Continue doing this. By the end of this, we must end up with all T's.
- Return the "breadCount"
No comments:
Post a Comment