Minimum count of indices to be skipped for every index of Array to keep sum till that index at most T

Minimum count of indices to be skipped for every index of Array to keep sum till that index at most T

Given an array, arr[] of size N and an integer T. The task is to find for each index the minimum number of indices that should be skipped if the sum till the ith index should not exceed T.

Examples:

Input: N = 7, T = 15, arr[] = {1, 2, 3, 4, 5, 6, 7}
Output: 0 0 0 0 0 2 3 
Explanation: No indices need to be skipped for the first 5 indices: {1, 2, 3, 4, 5}, since their sum is 15 and = T.
For the sixth index, indices 3 and 4 can be skipped, that makes its sum = (1+2+3+6) = 12.
For the seventh, indices 3, 4 and 5 can be skipped which makes its sum = (1+2+3+7) = 13.

Input: N = 2, T = 100, arr[] = {100, 100}
Output: 0 1

Approach: The idea is to use a map to store the visited elements in increasing order while traversing. Follow the steps below to solve the problem:

• Create an ordered map, M to keep a count of the elements before the ith index.
• Initialize a variable sum as 0 to store the prefix sum.
• Traverse the array, arr[] using the variable i
  • Store the difference of sum+arr[i] and T in a variable, d.
  • If the value of d>0, traverse the map from the end and select the indices with the largest elements until the sum becomes less than T. Store the number of elements required in a variable k.
  • Add arr[i] to sum and increment A[i] in M by 1.
  • Print the value of k.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h> using namespace std;    void skipIndices(int N, int T, int arr[]) {          int sum = 0;             map<int, int> count;             for (int i = 0; i < N; i++) {                              int d = sum + arr[i] - T;                              int k = 0;            if (d > 0) {                                          for (auto u = count.rbegin(); u != count.rend();                  u++) {                 int j = u->first;                 int x = j * count[j];                 if (d <= x) {                     k += (d + j - 1) / j;                     break;                 }                 k += count[j];                 d -= x;             }         }                     sum += arr[i];                     count[arr[i]]++;            cout << k << " ";     } }    int main() {          int N = 7;     int T = 15;     int arr[] = { 1, 2, 3, 4, 5, 6, 7 };             skipIndices(N, T, arr);        return 0; }

Output

0 0 0 0 0 2 3 

Time Complexity: O(N²)
Auxiliary Space: O(N)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.  To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.

In case you wish to attend live classes with industry experts, please refer DSA Live Classes

Adblock test (Why?)

Original page link

Best Cool Tech Gadgets

Top favorite technology gadgets