Calculating Village Size - codepath/compsci_guides GitHub Wiki

TIP102 Unit 7 Session 1 Standard (Click for link to problem statements)

Problem 1: Calculating Village Size

In the kingdom of Codepathia, the queen determines how many resources to distribute to each village based on its class. A village's class is equal to the number of digits in its population. Given an integer population, write a function get_village_class() that returns the number of digits in population.

  1. Implement the solution iteratively.
  2. Implement the solution recursively.
  3. Discuss: what are the similarities between the two solutions? What are the differences?

Problem Highlights

  • 💡 Difficulty: Easy
  • ⏰ Time to complete: 10-15 mins
  • 🛠️ Topics: Recursion, Iteration, Mathematical Operations

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?
  • Q: What is the main task in this problem?
    • A: The task is to determine the number of digits in the population number.
  • Q: Can the population be zero?
    • A: No, the problem assumes a positive integer population.
HAPPY CASE
Input: 432
Output: 3
Explanation: The number 432 has 3 digits.

Input: 9
Output: 1
Explanation: The number 9 has 1 digit.

EDGE CASE
Input: 1000
Output: 4
Explanation: The number 1000 has 4 digits.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Counting Digits in an Integer, we want to consider the following approaches:

  • Iteration: Use a loop to repeatedly divide the number by 10 and count how many times this operation can be performed before the number becomes zero.
  • Recursion: Use a base case for when the number becomes zero and a recursive case where the number is divided by 10, counting each step.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:

  • The number of digits in a number is equivalent to the number of times you can divide it by 10 before it becomes zero.

Iterative Approach:

1) Initialize a counter `count` to 0.
2) While `population` is greater than 0:
   a) Divide `population` by 10.
   b) Increment `count`.
3) Return `count` as the number of digits.

Recursive Approach:

1) Base case: If `population` is 0, return 0.
2) Recursive case: Return 1 plus the result of a recursive call with `population // 10`.

⚠️ Common Mistakes

  • Forgetting the base case in the recursive solution, which can lead to infinite recursion.
  • Not accounting for edge cases such as small populations.

4: I-mplement

Implement the code to solve the algorithm.

# Iterative Solution

def get_village_class_iterative(population):
    count = 0
    while population > 0:
        population //= 10
        count += 1
    return count

# Recursive Solution

def get_village_class_recursive(population):
    if population == 0:
        return 0
    return 1 + get_village_class_recursive(population // 10)

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

  • Trace through the get_village_class_iterative function with the input 432. The function should return 3 after dividing the number by 10 three times.
  • Trace through the get_village_class_recursive function with the input 432. The function should return 3 after recursively dividing the number by 10 three times.

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Similarities:

  • Both solutions correctly calculate the number of digits in a given population number.
  • Both methods operate by continuously dividing the number by 10.

Differences:

  • Space Complexity:

    • The iterative solution has a space complexity of O(1) because it uses a constant amount of extra space.
    • The recursive solution has a space complexity of O(N) due to the recursion stack, where N is the number of digits in the population.

  • Performance: The iterative solution is generally preferred for its constant space usage and simplicity in understanding and implementation. The recursive solution, while more elegant and expressive, could be limited by stack size in environments with a large number of digits.