Glacier Signal Fires
Imagine signal fires spreading across icy mountain ridges in a repeating pattern. At the very beginning, there is only one fire. Then each new ridge makes the pattern grow using the total from the stage before it.
Your job is to calculate how many fires are burning after a given number of ridges. This is a growth-pattern problem, so the answer comes from understanding how one stage changes into the next. The examples show that the total grows quickly, which means each new ridge is adding much more than just one extra fire.
For example, when ridges = 0, the answer is 1. When ridges = 2, the answer is 13. By the time ridges = 4, the total reaches 121. Those jumps show that the pattern is being built from the previous result again and again.
The important part is finding the rule that links each ridge count to the next one. Once you understand that growth rule, you can compute the total for any valid input.
Example Input & Output
Four responding ridges keep the rule, ending with one guiding fire plus triple the blaze from ridge three.
The second ridge adds a beacon and repeats the earlier lights three times.
Only the opening signal burns.
Algorithm Flow
Solution Approach
The trick to this problem is recognizing that the signal fires grow according to a geometric pattern. Instead of simulating every ridge (which would be slow for large inputs), we can find a direct mathematical formula for the total.
Looking at the examples, the totals jump from 1 at ridges = 0, to 4 at ridges = 1, to 13 at ridges = 2, and so on. This is the well-known closed form of the sum of a geometric series with a ratio of 3.
The pattern is 1 + 3 + 9 + ..., which is the sum of powers of three. A geometric series of this form has a clean formula, so we can compute the answer in constant time:
Let us break down the formula. The sum of 3^0 + 3^1 + ... + 3^ridges equals (3^(ridges + 1) - 1) / (3 - 1). Because the common ratio is 3, the denominator becomes 2, giving us the expression above.
Let us verify with the examples. When ridges = 0, we get (3^1 - 1) / 2 = (3 - 1) / 2 = 1. When ridges = 2, we get (3^3 - 1) / 2 = (27 - 1) / 2 = 13. And when ridges = 4, we get (3^5 - 1) / 2 = (243 - 1) / 2 = 121. All of these match the expected answers exactly.
This approach is much better than looping, because it works in O(1) time and O(1) space, no matter how large the ridge count becomes.
Best Answers
class Solution {
public int glacier_signal_fires(Object input) {
int ridges = (int) input;
return (int)((Math.pow(3, ridges + 1) - 1) / 2);
}
}Comments (0)
Join the Discussion
Share your thoughts, ask questions, or help others with this Challenge.