Day 20 of #geekstreak2024 challenge powered by Deutsche Bank and GeeksforGeeks!
𝐏𝐎𝐓𝐃: 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.
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)
𝐀𝐥𝐠𝐨𝐫𝐢𝐭𝐡𝐦:
1. Initialization:
-Start with a variable total_count initialized to 0. This variable will keep track of the total number of divided integers across all elements in the array.
2. Iterate through the Array:
- For each element in the array:
- Calculate how many parts this element can be divided into. This can be computed using:
count= element\k
- This can also be derived using integer division: count=element k−1/k
- This formula gives the correct number of parts because it effectively rounds up the result of the division.
3. Accumulate Counts: Add the count for the current element to total_count.
4. Return Result: After processing all elements, return total_count.
𝐒𝐨𝐮𝐫𝐜𝐞 𝐜𝐨𝐝𝐞:
class Solution {
public:
int totalCount(int k, vector<int>& arr) {
int count=0;
for(int i=0;i<arr.size();i ){
count =arr[i]/k;
if(arr[i]%k!=0) count ;
}
return count;
}
};
#geekstreak2024
#deutschebank
#GeeksforGeeks
🚀🚀