Remove equal Numbers using stack in C-CodePudding

i have a problem with this task

Suppose a sequence of integer numbers is given. If there exist three or more consecutive equal numbers in this sequence, the first group of such equal numbers is removed from the sequence. Such operation is repeated with the obtained sequence until there is nothing to remove. Compute the quantity of the items that will be removed. using STL stack Complexity must be O(n).

Example 1. In sequence {2, 3, 3, 3, 1}, the first group of equal numbers is {3, 3, 3}. After groups’ removal, the sequence will be {2, 1}, and there is nothing to remove.

Example 2. In sequence {3, 2, 2, 2, 3, 3, 3}, the first group of numbers to remove is {2, 2, 2}. Then the sequence will be {3, 3, 3, 3}, hence it is possible to remove the whole sequence.

i try make smth like this, it work if group lenth is only 3, but it very slow, and tests throw TIME OUT

#include <cstdio>
#include <stack>
int main()
{
    int x, res = 0;
    std::stack<int> st, tmp_st;
    scanf_s("%d", &x);
    while (x != -1) {
        st.push(x);
        tmp_st = st;
        while ((!tmp_st.empty()) && st.top() == tmp_st.top()) {
            tmp_st.pop();
        }
        if (st.size() - tmp_st.size() == 3) {
            res  = 3;
            st.swap(tmp_st);
        }
        scanf_s("%d", &x);
    }
    printf("%d", res);
    return 0;
}

UPD: "static" is not needed here

about my decision: each time an item is added, I save a copy of the original stack and look at how many times the item that was added occurred before in a row, if this number is equal to 3 (to be more, I need to improve the condition) then the items are also removed from the original stack, and the number of deleted items I output at the end in the standard output stream, also in the condition in the input can only be numbers from 0 to 9

UPD2: i make it work, but its steel slow

#include <cstdio>
#include <stack>
int main()
{
    int x = 0, res = 0, n = 1;
    std::stack<int> st, tmp_st;
    
    while (x != -1) {

        scanf_s("%d", &x);
        
        if (!st.empty()&&x != st.top()) {
            if (n < 3) 
            {
                st.push(x);
                tmp_st.push(n);
                n = 1;
                continue;
            }
            
                 res  = n;
                 while (n != 0) 
                 {
                    --n;
                    st.pop();
                 }
                 if (!tmp_st.empty()&&x != st.top()) 
                 {
                     n = 1;
                 }
                 else
                 {
                     if (x == -1) break;
                     n = tmp_st.top() 1;
                     tmp_st.pop();
                     
                 }
                 st.push(x);
                 continue;
                 
            
        }

        if (!st.empty() && x == st.top())
        {
              n;
            st.push(x);
        }

        if (st.empty()) 
        {
            st.push(x);
            n = 1;
        }
        
        
    }
    printf("%d", res);
    return 0;
}

CodePudding user response：

I would use one stack only and count the repitition of the last symbol until there comes another one. If the repition exeeds 3 you just pop 3 times. This will be O(2n) in worst case so you have O(n)

CodePudding user response：

Assumptions

I’m going to assume an “asymmetry” in the task, in particular that reversing the input may not, in general, yield a reverse of the result:

{ 3 2 2 2 3 3 3 } → { 3 3 3 3 } → { }
{ 3 3 3 2 2 2 3 } → { 2 2 2 3 } → { 3 }

In other words, you are not required to backtrack for an “optimal” (by the highest number of removed items) ordering of removals, but can instead take a “greedy” approach: Remove the first “removable” (long enough) sequence and repeat.

This↑↑↑ assumption is hugely important, because it makes a difference between an O(n) problem and an O(n²) problem.

Algorithm

One possible approach would be a cycle that

reads the next number item,
compares item to the top of the stack, and
- if equal, adds item to the stack,
- if not equal,
  - if the previous group of equal items on the stack is big enough,
    - pops the group from the stack, adding its size to the number of removed items, and then
  - adds the new item to the stack.

The implementation has a few distracting technicalities, such as “pre-collapsing” using a counter (top_count). But it is easy to see that the outer loop runs O(n) times and the inner loop does not increase the complexity, because (1) it cannot pop the stack more times than the number of items read from the input and (2) all code paths that don’t pop the stack cause the inner loop to exit. (The argument is quite similar to why Aho-Corasick is linear, just way simpler in this case.)

Code

This example lacks input error checking for the sake of brevity.

#include <cstdint>
#include <iostream>
#include <stack>
#include <tuple>

namespace {
constexpr std::size_t LIMIT{3};

std::size_t count_removed(std::istream& input) {
  std::stack<std::tuple<int, std::size_t>> stack;
  int item;
  if (input >> item) {
    stack.emplace(item, 1);
  } else {
    return 0;
  }
  std::size_t removed{};
  while (input >> item) {
    for (;;) {
      auto& [top_item, top_count]{stack.top()};
      if (item == top_item) {
          top_count;
        break;
      } else if (top_count >= LIMIT) {
        removed  = top_count;
        stack.pop();
        if (!stack.empty()) continue;
      }
      stack.emplace(item, 1);
      break;
    }
  }
  const auto& [top_item, top_count]{stack.top()};
  if (top_count >= LIMIT) removed  = top_count;
  return removed;
}
}  // namespace

int main() { std::cout << count_removed(std::cin) << '\n'; }

Examples and Tests

{ } → 0 (/0)
{ 1 } → 0 (/1)
{ 1 1 } → 0 (/2)
{ 1 1 1 } → 3 (/3)
{ }
{ 1 1 1 1 } → 4 (/4)
{ }
{ 3 2 2 2 3 3 3 } → 7 (/7)
{ 3 3 3 3 }
{ }
{ 3 3 3 2 2 2 3 } → 6 (/7)
{ 2 2 2 3 }
{ 3 }
{ 1 1 2 2 2 1 1 } → 7 (/7)
{ 1 1 1 1 }
{ }
{ 1 1 1 2 2 1 1 1 } → 6 (/8)
{ 2 2 1 1 1 }
{ 2 2 }
{ 1 1 2 2 2 1 1 1 2 2 } → 8 (/10)
{ 1 1 1 1 1 2 2 }
{ 2 2 }
{ 0 0 1 2 2 3 4 4 5 5 4 3 3 2 1 1 0 } → 0 (/17)
{ 0 0 1 2 2 3 4 4 5 5 5 4 3 3 2 1 1 0 } → 18 (/18)
{ 0 0 1 2 2 3 4 4 4 3 3 2 1 1 0 }
{ 0 0 1 2 2 3 3 3 2 1 1 0 }
{ 0 0 1 2 2 2 1 1 0 }
{ 0 0 1 1 1 0 }
{ 0 0 0 }
{ }
{ 0 1 1 2 2 2 3 3 3 3 2 2 2 1 1 4 4 4 4 } → 18 (/19)
{ 0 1 1 3 3 3 3 2 2 2 1 1 4 4 4 4 }
{ 0 1 1 2 2 2 1 1 4 4 4 4 }
{ 0 1 1 1 1 4 4 4 4 }
{ 0 4 4 4 4 }
{ 0 }
{ 0 0 1 2 2 3 3 3 2 1 1 2 2 3 3 3 2 1 0 } → 15 (/19)
{ 0 0 1 2 2 2 1 1 2 2 3 3 3 2 1 0 }
{ 0 0 1 1 1 2 2 3 3 3 2 1 0 }
{ 0 0 2 2 3 3 3 2 1 0 }
{ 0 0 2 2 2 1 0 }
{ 0 0 1 0 }
{ 1 1 2 2 3 3 3 4 3 3 3 2 1 } → 6 (/13)
{ 1 1 2 2 4 3 3 3 2 1 }
{ 1 1 2 2 4 2 1 }
{ 1 1 2 2 3 3 3 2 3 3 3 2 1 } → 9 (/13)
{ 1 1 2 2 2 3 3 3 2 1 }
{ 1 1 3 3 3 2 1 }
{ 1 1 2 1 }
{ 1 1 2 3 3 3 2 3 3 3 2 1 1 } → 13 (/13)
{ 1 1 2 2 3 3 3 2 1 1 }
{ 1 1 2 2 2 1 1 }
{ 1 1 1 1 }
{ }

CodePudding user response：

tmp_st = st is a performance killer. Copying the stack is not a constant time operation, but O(n) in terms of a stack length. This degrades the time complexity to quadratic. And you don't need to do it.

You only need to compare the number with the top of stack, and perhaps with one just below the top:

If the number compares not equal to the top, just push it.
Otherwise, tentatively pop, and compare the number to the new top
- If they compare not equal, there is no triplet. Push the number twice
- Otherwise, we have a triplet. Do not push anything, but keep reading and discarding for as long as you read the same value.