Dole Out Cadbury – TCS CodeVita

Count the total number of students who can receive Cadbury chocolates by distributing the largest possible square pieces from all chocolate bars in a given size range.

Understand the Problem

Problem Statement

In a school, a teacher is assigned to distribute Cadbury chocolates to students for Independence Day. The teacher has a box full of Cadbury chocolates with different widths and heights. He can only distribute the largest square shape Cadbury piece. So if he has a Cadbury of length 10 and width 5, then he needs to break the Cadbury in 5×5 square and distribute to the first student and then the remaining 5×5 square to the next student in the queue.

The program must accept four integers P, Q, R and S representing the minimum length, maximum length, minimum width and maximum width of Cadbury in the box as the input. The program must print the total number of students who will get the Cadbury as the output.

Constraints

1 ≤ P < Q ≤ 1500
1 ≤ R < S ≤ 1500
All inputs are positive integers
The chocolate dimensions will always be valid (length ≥ width for square distribution)
Output will fit within standard integer ranges

Examples

Example 1

Input

5 6 3 4

Output

Explanation

There are four possible sizes of Cadbury: 5×3, 5×4, 6×3, and 6×4. - 5×3: 4 students (3×3, 2×2, 1×1, 1×1) - 5×4: 5 students (4×4, 1×1, 1×1, 1×1, 1×1) - 6×3: 2 students (3×3, 3×3) - 6×4: 3 students (4×4, 2×2, 2×2) Total: 4 + 5 + 2 + 3 = 14 students

Example 2

Input

1 3 10 12

Output

Explanation

All combinations from 1×10 to 3×12 are considered: - 1×10, 1×11, 1×12: 10, 11, 12 students respectively - 2×10, 2×11, 2×12: 5, 22, 6 students respectively - 3×10, 3×11, 3×12: 10, 33, 12 students respectively Total: 10+11+12+5+22+6+10+33+12 = 67 students

Solution

#include <stdio.h>
#include <stdlib.h>

// Function to calculate GCD using Euclidean algorithm
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// Function to calculate number of students for given dimensions
int students_for_chocolate(int length, int width) {
    int g = gcd(length, width);
    return (length * width) / g;
}

int main() {
    int P, Q, R, S;
    scanf("%d %d %d %d", &P, &Q, &R, &S);
    
    int total_students = 0;
    
    // Iterate through all possible chocolate dimensions
    for (int length = P; length <= Q; length++) {
        for (int width = R; width <= S; width++) {
            total_students += students_for_chocolate(length, width);
        }
    }
    
    printf("%d\n", total_students);
    return 0;
}

Time:O((Q-P+1) × (S-R+1) × log(min(Q,S))) - The nested loops iterate through all possible dimensions, and each GCD calculation takes O(log(min(Q,S))) time.

Space:O(1) - Only uses a constant amount of extra space regardless of input size.

Approach:

The C solution implements the GCD-based approach:

gcd(): Implements Euclidean algorithm to find Greatest Common Divisor
students_for_chocolate(): Calculates number of students for given dimensions using formula (length*width)/gcd(length,width)
main(): Reads input, iterates through all dimensions, accumulates total students, and prints result

The algorithm efficiently calculates the result without simulating the actual cutting process.

Visual Explanation

Loading diagram...

All Problems