C++-এ O(1) এক্সট্রা স্পেস দিয়ে অ্যালটারনেটিং ধনাত্মক ও ঋণাত্মক আইটেমে রি-অ্যারেঞ্জ করুন

একটি পূর্ণসংখ্যার অ্যারে দেওয়া থাকলে, O(1) এক্সট্রা স্পেসে ধনাত্মক সংখ্যাগুলো ঋণাত্মক সংখ্যা দিয়ে ঘিরে থাকবে এমনভাবে রি-অ্যারেঞ্জ করতে হবে। fazla এলিমেন্ট শেষে থাকবে।

উদাহরণ

ইনপুট − arr[] = {-1,-2,-3,1,2,3}

আউটপুট − -1 1 -2 2 -3 3

ইনপুট − arr[] = {-1,-2,-3,1,2,3,5,5,-5,3,1,1}

আউটপুট − -1 1 -2 2 -3 3 -5 5 5 3 1 1

প্রোগ্রামে ব্যবহৃত পদ্ধতি

ptr = -1 ইনিশিয়ালাইজ করুন।
for i=0 to size-1: যদি ptr >= 0 এবং চিহ্ন আলাদা হয় (arr[i]>=0 && arr[ptr]<0 বা বিপরীত), তবে move_array(arr, size, ptr, i) কল করুন।
move_array-এ arr[temp] কে ptr পজিশনে শিফ্ট করুন।
যদি i-ptr >= 2 হয়, ptr += 2; অন্যথায় ptr = -1।
যদি ptr == -1 হয় এবং চিহ্ন পজিশনের সাথে মেলে, ptr = i।

উদাহরণ কোড

#include <iostream>
#include <assert.h>
using namespace std;

void move_array(int arr[], int size, int ptr, int temp){
    char ch = arr[temp];
    for(int i = temp; i > ptr; i--){
        arr[i] = arr[i - 1];
    }
    arr[ptr] = ch;
}

void Rearrangement(int arr[], int size){
    int ptr = -1;
    for(int i = 0; i < size; i++){
        if (ptr >= 0){
            if(((arr[i] >= 0) && (arr[ptr] < 0)) || ((arr[i] < 0) && (arr[ptr] >= 0))){
                move_array(arr, size, ptr, i);
                if(i - ptr >= 2) ptr = ptr + 2;
                else ptr = -1;
            }
        }
        if(ptr == -1){
            if (((arr[i] >= 0) && (!(i & 0x01))) || ((arr[i] < 0) && (i & 0x01))){
                ptr = i;
            }
        }
    }
}

int main(){
    int arr[] = {-1, -2, -3, 1, 2, 3};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Array before Arrangement: ";
    for (int i = 0; i < size; i++) cout << arr[i] << " ";
    Rearrangement(arr, size);
    cout << "\nRearrangement of an array in alternating positive & negative items with O(1) extra space is: ";
    for(int i = 0; i < size; i++) cout << arr[i] << " ";
    return 0;
}

আউটপুট

উপরের কোড রান করলে নিচের আউটপুট পাওয়া যাবে:

Array before Arrangement: -1 -2 -3 1 2 3 Rearrangement of an array in alternating positive & negative items with O(1) extra space is: -1 1 -2 2 -3 3