CODEWITHSUNDEEP
javastack
soumyaranjan tripathy
soumyaranjan tripathy

Reputation: 11

Delete the first half elements from stack of integer

You are given a stack with n integers. You need to delete floor(n/2) elements from the bottom of the stack and print the remaining elements of the stack. The remaining elements should be printed in the order that they are inserted into the stack.

floor(3.5) will give the output as 3, greatest integer less than or equal to the input. Input Format: The first line of input is an integer n denoting the size of stack. The next line contains n space separated integers. Output Format: The remaining elements of the stack after removal of the required elements. Example: Stack(bottom -> top) = [1, 2, 3, 4, 5, 6] Output: [4, 5, 6]

Stack = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] Output: [6, 7, 8, 9, 10, 11]

Sample Input: 12 1 2 3 4 5 6 7 8 9 10 11 12

Sample Output: [7, 8, 9, 10, 11, 12]

Sample input: 19 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

Sample Output: [10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

Here my problem is my code passed test case 1 and test case 2 but in test case 3 where sample input is 19 there is should be printing as mentioned above output but my output came [11, 12, 13, 14, 15, 16, 17, 18, 19] its omitting 10th element and i dont know where is my error. So please help me in this

MY Code -

import java.util.*;

public class DeleteElement {
    public static void main(String args[]) {
        Stack<Integer> stack = new Stack<>();
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        while (n-- > 0)
            stack.push(s.nextInt());
        deleteFirstHalf(stack, stack.size(), 0);
        System.out.println(stack);
    }

    static void deleteFirstHalf(Stack<Integer> stack, int n, int curr) {


        if(stack.empty() || curr == n) {
            return;
        }
        int x = stack.pop();

        deleteFirstHalf(stack, n, curr+1);

        if(curr<Math.floor(n/2)){
            stack.push(x);
        }
    }
}

Note - Don't change the main() in my code.

Upvotes: 0

Views: 1909

Answers (4)

hassan marzooq
hassan marzooq

Reputation: 36

I actually tried that with a Different Approach, where I created 2 different stacks temp and temp1, instead of recursively calling the function I had internal checks and printed the output at the end

static void deleteFirstHalf(Stack<Integer> stack) {
    Stack<Integer> temp = new Stack<Integer>();
    Stack<Integer> temp1 = new Stack<Integer>();
    int i = stack.size();
    int dest = stack.size() / 2;
    while (i-- > dest) {
        int t = stack.pop();
        temp.push(t);
      }
    while (!temp.empty()) {
        int t = temp.pop();
        // System.out.print(i + " size");
        temp1.push(t);
    }
    System.out.print(temp1);
}

Upvotes: 1

Divya Rawat
Divya Rawat

Reputation: 1

Instead of (curr<Math.floor(n/2)) try (curr < n-Math.floor(n/2))

Upvotes: 0

himansage
himansage

Reputation: 1

Instead of curr<Math.floor(n/2) try n-curr > Math.floor(n/2)

Upvotes: 0

a.deshpande012
a.deshpande012

Reputation: 744

Your bug comes from the fact that you're supposed to delete the bottom floor(n/2) elements, but instead you're keeping the top floor(n/2) elements. The reason it works for some test cases is that when n is even, keeping the top n/2 elements is the same as deleting the bottom n/2 elements. When n is odd, the code should keep one extra element.

The solution is to change if (curr < Math.floor(n/2)) to if (curr < n/2 + n%2). For one, you can drop the Math.floor(), since integer division does floor division anyway. The key difference is the addition of n%2. n%2 evaluates to 0 when n is even, and 1 when n is odd. What this does is if n is odd, it will make the code keep one extra element. (in the case of the 3rd test case, it will keep 10 instead of deleting it) If n is even, n%2 evaluates to 0, so the algorithm behaves the same as before.

Upvotes: 0

Related Questions