DSAPROB1 - Editorial

editorial
, ,
1

Problem link - Make Elements Divisible by K in

Problem Statement:

You are given an integer array nums nums of length N and an integer K. You can perform an operation where you add or subtract 1 from any array element. Your task is to determine the minimum number of operations required to make all elements of the array divisible by K.

Approach:

The key idea is to adjust each number in nums so that it becomes divisible by K in as few moves as possible. For any given number:

  • If it’s already divisible by K, no operations are needed.
  • If it’s not divisible by K, there are two choices:
    1. Increase the number by adding the difference to the next multiple of K.
    2. Decrease the number by subtracting the remainder to get to the previous multiple of K.

For each number, we choose the smaller of the two adjustments (increase or decrease) to minimize the number of operations.

Step-by-Step Explanation:

  1. Initialize a Counter:
    Start with total_operations = 0 to keep track of the total number of moves.
  2. Loop Through the Array:
    For each number in the array:
  • Find the remainder when the number is divided by K : remainder = num % K.
  • If the remainder is 0, the number is already divisible by K, so no operations are needed.
  • If the remainder is not 0, calculate the number of operations needed to either:
    • Increase the number: K - remainder.
    • Decrease the number: remainder.
  • Add the smaller of these two values to total_operations.
  1. Return the Result:
    After processing all numbers, return the total number of operations.

Time Complexity:

  • O(N): We only need to iterate through the array once, calculating the remainder and minimum operations for each number, making the time complexity linear with respect to the size of the array N.

Space Complexity:

  • O(1): We use only a few extra variables (total_operations, remainder), so the space usage is constant regardless of the size of the input array.