|
Given a sorted array arr[] and an integer P. Your task is to raise elements of arr[] to power of P and return them in sorted order in a new array.
Examples:Input: arr[] = {-20, -5, 1, 2, 8}, P=2
Output: 1 4 25 64 400
Explanation: When we square the values of arr we get 400,25,1,4,64 which then sorted will give us the values as [1,4,25,64,400]. We have to put these values in ans[].
Input: arr[] = {1, 3, 5, 7, 8}, P=2
Output: 1 27 125 343 512
Approach: To solve the problem, follow the below idea:
As the array arr is already sorted, some part will be sorted even after raising values to exponential P. If the exponential is even or all the values in arr is non negative .The order of the exponentially raised values will be the same. Otherwise there will be two parts we will be sorting one from start of arr to before the first non negative values and other from the non negative value to the end of arr. So will be using two pointer approach to solve the problem.
Step-by-step algorithm:- Count the number of negative numbers in sorted input array arr[].
- If cnt == zero or P is odd, then the order of arr[i] ^ P, will be same as arr[i].
- Otherwise, if cnt > 0 and P is even, then the relative position of the positive numbers will remain the same but the relative order of negative numbers will be reversed.
- For the positive numbers start from the index positive = cnt and move forward.
- For the negative numbers start from the index negative = cnt -1 and move backward.
- Find pVal by calculating arr[positive] ^ P
- Find nVal by calculating arr[negative] ^ P
- Push the smaller value to ans.
- After traversing over all the elements, return ans.
Below is the implementation of the algorithm:
C++
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
void exponentialSort(vector<int>& arr, vector<int>& ans,
int P)
{
int n = arr.size();
int cnt = 0;
// Count the number of negative elements in arr
for (int i = 0; i < n; i++) {
if (arr[i] < 0) {
cnt++;
}
}
// If there are no negative elements or the power is an
// odd number, then we can simply calculate the value
// for each index and store the result
if (cnt == 0 || P % 2 != 0) {
for (int i = 0; i < n; i++) {
ans[i] = pow(arr[i], P);
}
}
else {
// Place the positive pointer at the index from
// where the positive numbers start
int index = 0, positive = cnt;
// Place the negative pointer at the index from
// where the negative numbers end
int negative = positive - 1;
while (positive < n && negative >= 0) {
// Calculate the values at positive and negative
// pointers
int pVal = pow(arr[positive], P);
int nVal = pow(arr[negative], P);
// If the positive value is smaller, then push
// the positive value into ans
if (pVal < nVal) {
ans[index] = pVal;
positive++;
}
else {
// If the negative value is smaller, then
// push the negative value into ans
ans[index] = nVal;
negative--;
}
index++;
}
// Fill the exponent of remaining positive numbers,
// if any
while (positive < n) {
ans[index] = pow(arr[positive], P);
index++;
positive++;
}
// Fill the exponent of remaining negative numbers,
// if any
while (negative >= 0) {
ans[index] = pow(arr[negative], P);
index++;
negative--;
}
}
}
int main()
{
// Sample Input
vector<int> arr = { -4, -1, 0, 3, 5 };
// Array to store the sorted array
vector<int> ans(arr.size());
int P = 2;
exponentialSort(arr, ans, P);
for (int i = 0; i < ans.size(); i++) {
cout << ans[i] << " ";
}
cout << endl;
return 0;
}
// This code is contributed by shivamgupta0987654321
/*package whatever //do not write package name here */
import java.io.*;
class GFG {
public static void main(String[] args)
{
// Sample Input
int[] arr = { -4, -1, 0, 3, 5 };
// Array to store the sorted array
int[] ans = new int[arr.length];
int P = 2;
exponentialSort(arr, ans, P);
for (int i = 0; i < arr.length; i++)
System.out.print(ans[i] + " ");
}
// Function to perform the exponential sort
static void exponentialSort(int[] arr, int[] ans, int P)
{
int n = arr.length;
int cnt = 0;
// Count the number of negative elements in arr
for (int i = 0; i < n; i++) {
if (arr[i] < 0)
cnt++;
}
// If there are no negative elements or the power is
// an odd number then we can simply calculate the
// value for each index and print the answer
if (cnt == 0 || P % 2 != 0) {
for (int i = 0; i < n; i++) {
ans[i] = (int)Math.pow(arr[i], P);
}
}
else {
// Place the positive pointer at the index from
// where the positive numbers start
int index = 0, positive = cnt;
// Place the negative pointer at the index from
// where the negative numbers end
int negative = positive - 1;
while (positive < n && negative >= 0) {
// Calculate the values at positive and
// negative pointers
int pVal = (int)Math.pow(arr[positive], P);
int nVal = (int)Math.pow(arr[negative], P);
// If the positive value is smaller, then
// push the positive value into ans
if (pVal < nVal) {
ans[index]
= (int)Math.pow(arr[positive], P);
positive++;
index++;
}
else {
// If the negative value is smaller,
// then push the negative value into ans
ans[index]
= (int)Math.pow(arr[negative], P);
negative--;
index++;
}
}
// Fill the exponent of remaining positive
// numbers, if any
while (positive < n) {
ans[index]
= (int)Math.pow(arr[positive], P);
index++;
positive++;
}
// Fill the exponent remaining negative numbers,
// if any
while (negative >= 0) {
ans[index]
= (int)Math.pow(arr[negative], P);
index++;
negative--;
}
}
}
}
import math
def exponential_sort(arr, P):
n = len(arr)
cnt = 0
ans = [0]*n
# Count the number of negative elements in arr
for i in range(n):
if arr[i] < 0:
cnt += 1
# If there are no negative elements or the power is an odd number,
# then we can simply calculate the value for each index and store the result
if cnt == 0 or P % 2 != 0:
for i in range(n):
ans[i] = math.pow(arr[i], P)
else:
# Place the positive pointer at the index from where the positive numbers start
index = 0
positive = cnt
# Place the negative pointer at the index from where the negative numbers end
negative = positive - 1
while positive < n and negative >= 0:
# Calculate the values at positive and negative pointers
p_val = math.pow(arr[positive], P)
n_val = math.pow(arr[negative], P)
# If the positive value is smaller, then push the positive value into ans
if p_val < n_val:
ans[index] = p_val
positive += 1
else:
# If the negative value is smaller, then push the negative value into ans
ans[index] = n_val
negative -= 1
index += 1
# Fill the exponent of remaining positive numbers, if any
while positive < n:
ans[index] = math.pow(arr[positive], P)
index += 1
positive += 1
# Fill the exponent of remaining negative numbers, if any
while negative >= 0:
ans[index] = math.pow(arr[negative], P)
index += 1
negative -= 1
return ans
# Driver Code
arr = [-4, -1, 0, 3, 5]
P = 2
ans = exponential_sort(arr, P)
for i in ans:
print(i, end=" ")
print()
function exponentialSort(arr, P) {
let n = arr.length;
let ans = new Array(n).fill(0);
let cnt = 0;
// Count the number of negative elements in arr
for (let i = 0; i < n; i++) {
if (arr[i] < 0)
cnt++;
}
// If there are no negative elements or the power is an odd number,
// calculate the value for each index
if (cnt === 0 || P % 2 !== 0) {
for (let i = 0; i < n; i++) {
ans[i] = Math.pow(arr[i], P);
}
} else {
let index = 0, positive = cnt;
let negative = positive - 1;
while (positive < n && negative >= 0) {
let pVal = Math.pow(arr[positive], P);
let nVal = Math.pow(arr[negative], P);
if (pVal < nVal) {
ans[index] = Math.pow(arr[positive], P);
positive++;
index++;
} else {
ans[index] = Math.pow(arr[negative], P);
negative--;
index++;
}
}
// Fill the exponent of remaining positive numbers, if any
while (positive < n) {
ans[index] = Math.pow(arr[positive], P);
index++;
positive++;
}
// Fill the exponent remaining negative numbers, if any
while (negative >= 0) {
ans[index] = Math.pow(arr[negative], P);
index++;
negative--;
}
}
return ans;
}
// Sample Input
let arr = [-4, -1, 0, 3, 5];
let P = 2;
let ans = exponentialSort(arr, P);
console.log(ans.join(' '));
Time Complexity: O(N * logP), where N is the number of elements in arr[] and P is the exponent.
Auxiliary Space: O(N)
|
