একটি পূর্ণসংখ্যার অ্যারে দেওয়া থাকলে, O(n) টাইম ও O(1) এক্সট্রা স্পেসে ধনাত্মক ও ঋণাত্মক সংখ্যা পরিবর্তনশীল পজিশনে আনার হবে। fazla এলিমেন্ট শেষে থাকবে।
উদাহরণ
ইনপুট − arr[] = {4, 2, -1, -1, 6, -3}
আউটপুট − 2 -1 6 -1 4 -3
ইনপুট − arr[] = {-1, -2, -3, 1, 2, 3, 5, 5, -5, 3, 1, 1}
আউটপুট − 2 -2 3 -5 5 -3 5 -1 1 3 1 1
প্রোগ্রামে ব্যবহৃত পদ্ধতি
প্রথমে সব ঋণাত্মক সংখ্যা সামনে আনার জন্য
temp = -1থেকে শুরু করেswap(arr[++temp], arr[i])করুন।positive = temp+1,negative = 0।while(positive < size && negative < positive && arr[negative] < 0)লুপেswap(arr[negative], arr[positive])করুন।positive++,negative += 2।
উদাহরণ কোড
#include <bits/stdc++.h>
using namespace std;
void Rearrangement(int arr[], int size){
int temp = -1;
for(int i = 0; i < size; i++){
if (arr[i] < 0){
temp++;
swap(arr[temp], arr[i]);
}
}
int positive = temp + 1;
int negative = 0;
while(positive < size && negative < positive && arr[negative] < 0){
swap(arr[negative], arr[positive]);
positive++;
negative += 2;
}
}
int main(){
int arr[] = {4, 2, -1, -1, 6, -3};
int size = sizeof(arr)/sizeof(arr[0]);
Rearrangement(arr, size);
cout << "Rearrangement of positive and negative numbers in O(n) time and O(1) extra space is: ";
for(int i = 0; i < size; i++) cout << arr[i] << " ";
return 0;
}
আউটপুট
উপরের কোড রান করলে নিচের আউটপুট পাওয়া যাবে:
Rearrangement of positive and negative numbers in O(n) time and O(1) extra space is: 2 -1 6 -1 4 -3
