AtCoder Beginner Contest 43: Problem A - Children and Candies Solved! (Two Approaches)

 Hey there, problem solvers! Today we're tackling Problem A from AtCoder Beginner Contest 43: Children and Candies.

This problem might seem straightforward at first glance, but it offers an opportunity to explore two solutions with different time complexities. Let's dive in!

The Problem Statement

Mr. Evi at AtCoder Kindergarten is a generous soul. He's lining up N children and giving them candies based on their position. The first child receives 1 candy, the second 2 candies, and so on, until the Nth child receives N candies. Your task is to find the total number of candies Mr. Evi will need.

The problem also specifies that N can range from 1 to 100.

Solution 1: Brute Force Loop (Linear Time)

This is a classic approach for problems where you need to iterate through a sequence and perform a calculation on each element. Here's how it works:

1. Looping Through Children: We'll use a loop that iterates from 1 to N (number of children).
2. Calculating Candies: Inside the loop, for each child (represented by the variable i), we'll calculate the number of candies they receive based on the formula candies = i.
3. Accumulating Total: We'll keep track of the total number of candies given so far using a variable called total_candies. In each iteration, we'll add the current child's candies (candies) to the total_candies variable.

This approach is easy to understand and implement, but its time complexity is O(N). This means as the number of children increases, the time it takes to calculate the total candies will also increase linearly.

Here's the code snippet for the same:

int n = take input;
int ans = 0;
for(int i = 1; i <= n; i++)
	ans += i;

Solution 2: Mathematical Formula (Constant Time)

This approach takes advantage of the fact that the number of candies forms an arithmetic series (AP). An arithmetic series is a sequence of numbers where the difference between consecutive terms is constant (in this case, 1 candy).

The beauty of arithmetic series is that we have a formula to calculate the sum of its terms without iterating through each element. This formula is:

sum = n * (a + (n-1)d) / 2

where:

• n is the number of terms (number of children)
• a is the first term (1 candy)
• d is the common difference (1)

In our case, a is 1 and d is equal to 1 since the difference between adjacent elements is 1. Plugging these values into the formula, we get:

sum = n * (n + 1) / 2

This formula allows us to calculate the total number of candies in constant time (O(1)), regardless of the number of children (N).

Here's the code snippet for the same:

int n = take input;
print(n * (n+1) / 2);

Watch the video in case you still have any doubts :)