2620. Counter


Problem Description

The problem requires us to write a function that generates a "counter" function. When the counter function is first called, it should return an integer n which is given as input when creating the counter. On each subsequent call, the counter function should return an integer that is one greater than the value it returned on the previous call. Essentially, it keeps track of a count, starting from n and increasing by 1 each time it is invoked.

Intuition

Our goal is to retain the state between function calls. To achieve this, we can use closure properties in the JavaScript-related TypeScript language. A closure is an inner function that has access to the outer (enclosing) function's variablesā€”scope chain. The closure has three scope chains: it has access to its own scope, the outer functionā€™s variables, and the global variables.

The enclosed variable i is initialized with the value of n and is kept alive after the createCounter function execution context is popped off the call stack. In other words, every time the inner function is called, it has access to the i variable that was defined in the same context.

The intuition behind the solution is:

  • Define a variable i inside the createCounter function's scope and set its initial value to n.
  • Return an inner function that increments and returns the variable i when called.
  • Since each call to the inner function will retain the reference to i, it will keep incrementing i by 1 each time without resetting it.

The elegant part of the solution is utilizing the closure's ability to maintain state across multiple calls without the need for an external state manager or object.

Solution Approach

The implementation of the solution is straightforward due to TypeScript's support for closuresā€”a key concept in functional programming.

Here is the step-by-step approach of the solution:

  • First, we define a function createCounter that takes an integer n as an argument.
  • Within createCounter, we initialize a variable i with the value of the argument n. This variable i will serve as our counter state.
  • We then define and return an inner functionā€”this is where our closure comes into play. This inner function has access to i because i is in the scope of the outer function createCounter.
  • In this inner function, we increase the value of i by 1 using the increment operator ++. This operator increases i by one and then returns the original value of i before the increment.
  • As a result, every time the returned inner function is called, it will increment i and then return its current value.

The key algorithmic concept at work here is the use of a closure that captures the local variable i from its surrounding scope in createCounter, allowing the inner function to have a persistent state across its invocations. This pattern effectively creates a private counter variable that is only accessible and modifiable by the returned function.

The important thing to note is that TypeScript, like JavaScript, treats functions as first-class citizens, meaning that functions can be assigned to variables, passed as arguments to other functions, and can be returned from functions as well. This feature is what enables us to create and return the inner function that acts as our counter.

The corresponding TypeScript code implementing the solution would be:

function createCounter(n: number): () => number {
    let i = n;
    return function () {
        return i++;
    };
}

By calling createCounter(10), we create a counter that starts at 10. Each call to the returned function will then provide the next number in the sequence (10, 11, 12, and so on), showcasing the closure's ability to maintain and update the counter state.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with a simple example. We'll use createCounter to generate a counter that starts at 5 and then call the counter function a few times to see how it increments the internal count.

  1. We call createCounter(5), which initializes the variable i to 5 within its scope and sets up the closure. This call returns a new functionā€”let's call it myCounter.

  2. We call myCounter() for the first time. Since i was initialized to 5, the function increments i to 6 but returns the original value of i, which is 5.

  3. We call myCounter() again. This time, i starts at 6, increments to 7, and then returns 6.

  4. We call myCounter() a third time. Now, i starts at 7, increments to 8, and then returns 7.

Here's how that would look in code:

// Step 1: We create the counter starting at 5.
let myCounter = createCounter(5);

// Step 2: We call the counter for the first time.
console.log(myCounter()); // Output: 5

// Step 3: We call the counter for the second time.
console.log(myCounter()); // Output: 6

// Step 4: We call the counter for the third time.
console.log(myCounter()); // Output: 7

// If we keep calling myCounter(), it will continue to output the next integer in the sequence.

Each call to myCounter() persistently increases the variable i by 1. Despite multiple invocations, the counter retains its current value thanks to the closure capturing the i variable. This behavior allows myCounter to act like a true "counter", demonstrating the effective use of closures in TypeScript to maintain state between function invocations.

Solution Implementation

1def create_counter(initial_count):
2    """
3    Creates a counter function that, when called, will return a number that increments by 1
4    each time the counter function is called.
5
6    :param initial_count: The starting point for the counter
7    :return: A function that when invoked, returns an incremented number
8    """
9    # Variable 'current_count' holds the current state of the counter
10    current_count = initial_count
11
12    # The returned function encapsulates the 'current_count' variable.
13    # Each time it is called, it increments 'current_count' by one, then returns the new value.
14    def counter():
15        nonlocal current_count
16        current_count += 1
17        return current_count - 1
18
19    return counter
20
21# Example usage:
22# Create a counter starting at 10
23counter = create_counter(10)
24print(counter())  # Should output: 10
25print(counter())  # Should output: 11
26print(counter())  # Should output: 12
27
1import java.util.function.IntSupplier;
2
3/**
4 * Creates a counter function that, when called, will return a number that
5 * increments by 1 each time the counter function is called.
6 *
7 * @param initialCount The starting point for the counter.
8 * @return An IntSupplier that when invoked, returns an incremented number.
9 */
10public class CounterCreator {
11
12    public static IntSupplier createCounter(int initialCount) {
13        // An array is used to hold the current state of the counter, as we need a final or effectively final variable
14        // to be used in the lambda's closure, but we need to alter it.
15        final int[] currentCount = {initialCount};
16
17        // The lambda expression encapsulates the 'currentCount' variable. Each time it is called,
18        // it increments the value at currentCount[0] by one, then returns the updated value.
19        return () -> currentCount[0]++;
20    }
21
22    // Example usage:
23    public static void main(String[] args) {
24        // Create a counter starting at 10
25        IntSupplier counter = createCounter(10);
26        System.out.println(counter.getAsInt()); // Should output: 10
27        System.out.println(counter.getAsInt()); // Should output: 11
28        System.out.println(counter.getAsInt()); // Should output: 12
29    }
30}
31
1#include <iostream>
2#include <functional>
3
4/**
5 * Creates a counter function that, when called, will return a number that
6 * increments by 1 each time the counter function is called.
7 *
8 * @param initialCount The starting point for the counter.
9 * @return A function object (lambda) that, when invoked, returns an incremented number.
10 */
11std::function<int()> createCounter(int initialCount) {
12    // Variable 'currentCount' holds the current state of the counter.
13    int currentCount = initialCount;
14
15    // The returned function object (lambda) encapsulates the 'currentCount' variable.
16    // Each time it is called, it increments the value of 'currentCount' by one,
17    // then returns the updated value.
18    // Captures 'currentCount' by reference so that the counter state persists across calls.
19    return [&currentCount]() -> int {
20        return currentCount++;
21    };
22}
23
24// Example usage:
25int main() {
26    // Create a counter starting at 10.
27    auto counter = createCounter(10);
28
29    // The counter retains its state across calls because 'currentCount' is captured by reference.
30    std::cout << counter() << std::endl; // Should output: 10
31    std::cout << counter() << std::endl; // Should output: 11
32    std::cout << counter() << std::endl; // Should output: 12
33
34    return 0;
35}
36
1/**
2 * Creates a counter function that, when called, will return a number that
3 * increments by 1 each time the counter function is called.
4 *
5 * @param {number} initialCount - The starting point for the counter.
6 * @returns {Function} A function that when invoked, returns an incremented number.
7 */
8function createCounter(initialCount: number): () => number {
9    // Variable 'currentCount' holds the current state of the counter.
10    let currentCount = initialCount;
11
12    // The returned function encapsulates the 'currentCount' variable. Each time it is called,
13    // it increments the value of 'currentCount' by one, then returns the updated value.
14    return function (): number {
15        return currentCount++;
16    };
17}
18
19// Example usage:
20// Create a counter starting at 10.
21const counter = createCounter(10);
22console.log(counter()); // Should output: 10
23console.log(counter()); // Should output: 11
24console.log(counter()); // Should output: 12
25

Time and Space Complexity

Time Complexity: The time complexity of the counter function is O(1), which is a constant time operation. Every time the function is called, it performs one increment operation and returns the new value.

Space Complexity: The space complexity of createCounter can also be considered O(1) since it creates a single closure with a variable i that maintains the state, no matter how many times the counter function is called. The counter itself does not allocate any additional space that is dependent on the input size n or the number of times it's called.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?


Recommended Readings

Want a Structured Path to Master System Design Too? Donā€™t Miss This!


Load More