Total count

You are given an array arr[] of positive integers and a threshold value k. For each element in the array, divide it into the minimum number of small integers such that each divided integer is less than or equal to k. Compute the total number of these integer across all elements of the array.

Examples:

Input: k = 3, arr[] = [5, 8, 10, 13]
Output: 14
Explanation: Each number can be expressed as sum of different numbers less than or equal to k as 5 (3 + 2), 8 (3 + 3 + 2), 10 (3 + 3 + 3 + 1), 13 (3 + 3 + 3 + 3 + 1). So, the sum of count of each element is (2+3+4+5)=14.

Input: k = 4, arr[] = [10, 2, 3, 4, 7]
Output: 8
Explanation: Each number can be expressed as sum of different numbers less than or equal to k as 10 (4 + 4 + 2), 2 (2), 3 (3), 4 (4) and 7 (4 + 3).So, the sum of count of each element is (3 + 1 + 1 + 1 + 2) = 8.

Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)

Constraints:
1 ≤ arr.size() ≤ 10⁵
0 ≤ arr[i] ≤ 10⁵
1 ≤ k ≤ 10⁵

Approach 01:

#include <iostream>
#include <vector>
#include <sstream>
#include <string>
using namespace std;

class Solution {
public:
    // Function to calculate the total number of steps required
    int totalCount(int divisor, vector<int>& numbers) {
        int totalSteps = 0;
        for (int i = 0; i < numbers.size(); ++i) {
            totalSteps += (numbers[i] + divisor - 1) / divisor;
        }
        return totalSteps;
    }
};

class Solution:
    # Function to calculate the total number of steps required
    def totalCount(self, divisor, numbers):
        totalSteps = 0
        for number in numbers:
            totalSteps += (number + divisor - 1) // divisor
        return totalSteps

Time Complexity

• Loop Iteration:

  The function iterates over all the elements in the input vector numbers. For each element, it performs a division and addition operation, both of which are constant-time operations. Given that the input vector has \(n\) elements, the time complexity is \(O(n)\), where \(n\) is the number of elements in the numbers vector.

• Overall Time Complexity:

  The overall time complexity is \(O(n)\), where \(n\) is the size of the numbers vector.

Space Complexity

• Auxiliary Space:

  The function uses a constant amount of space for the variable totalSteps and a few temporary variables for iteration, all of which are independent of the input size. Thus, the auxiliary space complexity is \(O(1)\).

• Input Space:

  The input vector numbers is passed by reference, so no additional space is used to store the input.

• Overall Space Complexity:

  The overall space complexity is \(O(1)\), since the space used by the function does not depend on the size of the input.