Teaching Kids Programming: Number of Positions in Line of People

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given integers n, a and b. You are standing in a line of n people. You don’t know which position you’re in, but you know there are at least a people in front of you and at most b people behind you. Return the number of possible positions you could be in.

Example 1
Input
n = 10
a = 3
b = 4
Output
5

Explanation
There’s 10 people and at least 3 are in front and at most 4 are behind.

This means you can be in indexes [0, 1, 2, 3, 4]. For example, at index 0, 9 people are in front, 0 are behind.

Hints:
check if overlap of front condition and back condition occurs.

Simulation Algorithm: Compute the Number of Positions in Line of People

We can increment the answer (number of possible positions) as soon as two conditions are met:

1
2
3
4
5
6
7

class Solution:
    def numberOfPositions(self, n, a, b):
        i = ans = 0
        while i < n - a and i <= b:
            ans += 1
            i += 1
        return ans

class Solution:
    def numberOfPositions(self, n, a, b):
        i = ans = 0
        while i < n - a and i <= b:
            ans += 1
            i += 1
        return ans

However, this may take time as the time complexity is O(N) in the worst case.

Math: Compute the Number of Positions in Line of People

From the above simulation algorithms, we see that the loop will break when i is incremented to the min values of (b + 1) and (n – a). Thus, we can do this mathematically.

1
2
3
4

class Solution:
    def numberOfPositions(self, n, a, b):
        ans = min(n - a , b + 1)
        return ans

class Solution:
    def numberOfPositions(self, n, a, b):
        ans = min(n - a , b + 1)
        return ans

The time complexity is O(1) constant.

–EOF (The Ultimate Computing & Technology Blog) —