0

we cannot use more than one DS. time complexity O(n).

Objective: all negative elements on left and positive on right.

No sorting please.

I am trying this but don't know what is wrong in here.

Please help a bit!

I am quite sure all cases are being taken care off!

        #include <iostream>

        using namespace std;

          int main(void){

           int arr[100], n, temp=0;

          cout << "Enter the size of array";
          cin >> n;

          for(int i=0; i<n; i++){

             cout << "Enter elements of array";
             cin >> arr[i];

          }

               int j=0;

            for(int k=n-1; k>=j; k--) {

    if(arr[j]<0 && arr[k]>=0) {

            j++;
    }

            if(arr[j]>=0 && arr[k]<0) {

                    temp = arr[k];
                    arr[k] = arr[j];
                    arr[j] = temp;
                    j++;
            }

                    if(arr[j]<0 && arr[k]<0) {

                            j++;
                            k++;

                    }

                            if(arr[j]>=0 && arr[k]>=0) {

                                    continue;

                            }

              }

            cout << arr;

             }
  • What is not working? What have you tried so far? – Carol Skelly Sep 29 '16 at 13:25
  • 1
    [accessing an index in an array in handlebars](http://stackoverflow.com/questions/8044219/how-do-i-access-an-access-array-item-by-index-in-handlebars) looks like a similar problem. – worc Sep 29 '16 at 23:31
  • Why don't update your context object before, to meet what you need? I mean, filter the `animals_data` object before calling `template(animals_data)`; – jherax Sep 30 '16 at 00:04
  • ... for example: `var firstAnimal = (animals_data.category[0] || {}).animals[0];` and then `template(firstAnimal)`, so you have to update your template, because you will not be iterating over an array but an object. – jherax Sep 30 '16 at 00:09
  • @vivek_gupta you have to update the template, you are not iterating over `categories`, not even `animals`, the context `firstAnimal` contains only the object at the first element in the array. You have to update your template. – jherax Oct 02 '16 at 18:54
  • @vivek_gupta try using this tool: **http://tryhandlebarsjs.com/** – jherax Oct 02 '16 at 18:55
  • @vivek_gupta Hey, what do you really need? Display only 1st animal from each `animals` array? So Snake, Cat, American flamingo,...? – lbartolic Oct 12 '16 at 08:23
  • Why no sorting? There are O(n) sorts that will solve this problem of yours every time. – Patrick87 Aug 16 '17 at 14:08
  • constraint! cannot use it. just arrangements. –  Aug 16 '17 at 14:40
  • It is an odd constraint. Any algorithm that solves this problem is equivalent to a sorting algorithm with the hard-coded comparison function `compare(int lhs, int rhs) { if (sign(lhs) < sign(rhs)) return -1; else if (sign(lhs) == sign(rhs)) return 0; else return 1; }`... whether you want to call your algorithm a sorting function or not, that is what it's doing: sorting based on the sign of the element. – Patrick87 Aug 16 '17 at 16:44
  • hey!. It's not me calling it like this. It's given. Just for Information: Appeared in Microsoft interview. can you please tell me what I am doing wrong here? or any possible solution? –  Aug 16 '17 at 16:49

1 Answers1

1

You don't say what you want done with zeroes; this assumes zeroes are ignored and their position doesn't matter. if zeroes should be treated as positives, or negatives, or if they should appear in the middle and not in arbitrary positions, some of the details below will need to be adjusted, but this will get you basically where you want to go.

  1. Starting on the left, scanning right, find the first positive number. We will call its zero-based index i. If no positive number is found, terminate the algorithm.
  2. Starting on the right, scanning left, find the first negative number. We will call its zero-based index j. If no negative number is found, terminate the algorithm.
  3. Iff i < j, swap elements at indices i and j, and recursively solve the same problem for the slice of the array from i+1 to j-1, inclusive (if i+1 >= j-1, you may simply terminate).

This is guaranteed to solve your problem correctly. The proof is by mathematical induction on the length of the array.

Base case: empty arrays and arrays of length 1 already satisfy the desired property with no swapping required. The algorithm looks at such arrays and does nothing too them.

Induction hypothesis: assume that all arrays of up to k elements are correctly processe by the algorithm; that is, the algorithm moves all negative elements to the left and all positive elements to the right.

Induction step: we must show that the algorithm correctly handles arrays of length k+1. Suppose the array of k+1 elements already satisfies the property. Our algorithm looks at all elements and does nothing. Suppose instead that there is at least one element out of place. That means there is a positive number with a negative number to the right of it. In particular, there is a leftmost positive number with a negative number to the right of it. Similarly, there is a rightmost negative number with a positive number to the left of it. Our algorithm swaps these two numbers, creating an array where these numbers are no longer out of place. Since we assumed the leftmost and rightmost positive and negative numbers, any other swaps must occur inside the numbers we just swapped. Our algorithm processes this part of the array, which has size at most k+1-2 = k-1, which, by the hypothesis, our algorithm handles correctly. QED

Pseudocode of an iterative implementation:

i = 0
j = n-1
while i < j do
    while !(array[i] > 0) do
        i = i + 1
    while !(array[j] < 0) do
        j = j - 1
    if i < j then
        tmp = array[i]
        array[i] = array[j]
        array[j] = tmp

If you want to treat zeroes as negatives, change array[j] < 0 to array[j] <= 0. If you want to treat zeroes as positives, change array[i] > 0 to array[i] >= 0. If you want zeroes in the middle, then run the above pseudocode three times: once to swap negatives and positives, once to swap negatives and zeros, and one to swap positives and zeroes.

Patrick87
  • 27,682
  • 3
  • 38
  • 73
  • O as positives only. I got this but the thing is the code is not printing what I want. I have updated the code above. If you can point out the mistake it will helpful. –  Aug 17 '17 at 10:32
  • @vivek_gupta Consider the array `[-1,1,-1]`. Your code will error out on this input since it will increment `k` to `3` and then try to access that undefined element. In fact, I think that whole middle condition is very suspect. If you are looking at `arr[i]` and `arr[k]` and both are negative, why should it be the case that your window remains the same size and shifts one to the right? Why not one to the left? Why not make the window smaller? Please explain your thinking there because I think you'll find it's flawed (as it is, it will even produce errors/undefined behavior). – Patrick87 Aug 17 '17 at 12:45
  • I have incremented k there becz when my if condition ends the main loop will decrement k which I don't want as in your array 3rd element is negative. so, as I increment it will be reduced further which will bring k at the same position to check the applicable if condition. But yes it will access an undefined element. Noted. Thanks. –  Aug 17 '17 at 14:03