Persistent Systems’ Sr Python Developer Hiring Challenge (2025)

Fitness Challenge (100 Marks)

Samantha and Jessica are two sisters who are preparing for their annual fitness challenge. They both have been assigned a personal trainer who has given them a workout plan for the next few weeks.

The plan includes a set of N exercises, and for each exercise, there is a recommended number of sets and repetitions. Samantha and Jessica have been keeping track of the number of sets and repetitions they have completed for each exercise.

At the end of each day, they compare their progress by calculating the sum of squared differences in the number of repetitions they completed for each exercise. However, they noticed that their progress is not always the same, and they want to make sure they are both making equal progress towards their fitness goals.

To achieve this, they decided to modify their workout plans. Samantha can modify the recommended number of repetitions for each exercise by +1 or -1 at most k1 times, and Jessica can modify the recommended number of repetitions for each exercise by +1 or -1 at most k2 times.

They want to minimize the sum of squared differences in their progress while still following their modified workout plans. Can you help them find the minimum sum of squared difference after modifying their workout plans?

Input Format

• The first line of the input contains three space-separated integers N, k1, k2.
• The second line contains N space-separated integers rep1[i].
• The third line contains N space-separated integers rep2[i].

Constraints

• 1 <= N <= 10^5
• 0 <= rep1[i], rep2[i] <= 10^5
• 0 <= k1, k2 <= 10^5

4 0 1
1 4 3 2
2 9 5 4

25
Explanation
Decrease rep2[1] by 1.

The sum of squared difference now becomes (2-1)^2 + (8-4)^2 + (5-3)^2 + (4-2)^2 = 25.

Time Limit(X):
0.50 sec(s) for each input.

Memory Limit:
512 MB

Source Limit:
100 KB

Allowed Languages:
Python, Python 3, Pypy, pyp

import sys
import heapq

def minimize_squared_difference(N, k1, k2, rep1, rep2):
    # Step 1: Calculate absolute differences
    diff = [abs(rep1[i] - rep2[i]) for i in range(N)]
    
    # Step 2: Create a max heap
    max_heap = [-d for d in diff]  # Use negative values for max heap
    heapq.heapify(max_heap)
    
    # Total operations available
    total_operations = k1 + k2
    
    # Step 3: Use the operations to minimize differences
    while total_operations > 0 and max_heap:
        largest_diff = -heapq.heappop(max_heap)  # Extract max (remember, it's negative)
        
        if largest_diff > 0:
            largest_diff -= 1  # Reduce the largest difference
            total_operations -= 1
        heapq.heappush(max_heap, -largest_diff)  # Push the modified difference back
    
    # Step 4: Calculate the final sum of squared differences
    return sum((-d) ** 2 for d in max_heap)

# Main function to read input and produce output
if __name__ == "__main__":
    # Reading input
    input_data = sys.stdin.read().strip().split('\n')
    N, k1, k2 = map(int, input_data[0].split())
    rep1 = list(map(int, input_data[1].split()))
    rep2 = list(map(int, input_data[2].split()))
    
    # Solve and print result
    result = minimize_squared_difference(N, k1, k2, rep1, rep2)
    print(result)

Complexity

1. Time Complexity:
   • Building the heap: O(N)O(N)O(N).
   • Modifying the largest difference: O((k1+k2)log⁡N)O((k1 + k2) \log N)O((k1+k2)logN).
   • Total: O(N+(k1+k2)log⁡N)O(N + (k1 + k2) \log N)O(N+(k1+k2)logN).
2. Space Complexity:
   • The heap requires O(N)O(N)O(N) space.