Write a function that takes a slice of integers and a target value, then returns how many times the target appears.
countTarget(nums, target)
Your solution should scan the list exactly once and make a decision about each element. This is your first chance to write code with a predictable, linear time complexity.
Input format: space-separated integers; the last value is the target.
countTarget([]int{3, 5, 3, 9, 3}, 3) // → 3
countTarget([]int{1, 2, 4, 8, 16}, 3) // → 0
countTarget([]int{1, 1, 1, 1}, 1) // → 4
countTarget([]int{}, 5) // → 0
You need to count how many times a value shows up in a list. There's no shortcut — you have to look at every element, since skipping one could skip a match. Sometimes the straightforward approach really is the efficient one, and this is a good first example of that.
Each comparison is a fixed, tiny amount of work. Do that once per element, and the total work grows in direct proportion to the list size — double the list, double the work. That's what "linear," or O(n), means.
Notice what you're not doing: you're not comparing every element to every other element (that would be quadratic), and you're not building an extra data structure (that would cost memory for no benefit here). One pass, one counter, is both necessary and enough.
Whenever you meet a new problem, ask: "can I answer this by looking at each element once, updating a small running total as I go?" If yes, you're looking at an O(n) solution — about as good as it gets when you must touch every input. Later problems will show naive approaches that check every pair (O(n²)), and cases where a hash map pulls that back down to O(n). This problem is the anchor: do a fixed amount of work per element, once.
def count_target(nums, target):
count = 0
for num in nums:
if num == target:
count += 1
return count
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.