Given an integer array arr[] of size N that is sorted in increasing order and an integer K, Return an array with power of K of each number sorted in increasing order.
Examples:
Input: arr[]: {-4, -1, 0, 3, 10}, K = 4
Output: {0, 1, 81, 256, 10000}
Explanation: After doing power of 4 operation,
the elements array will become {256, 1, 0, 81, 10000},
After sorting thearray will become {0, 1, 81, 256, 10000}.Input: arr[]: {-7, -3, 2, 3, 11}, K = 4
Output: {16, 81, 81, 2401, 14641}
Naive Approach: The basic idea is:
Firstly perform power of K operation on the all the elements of the array and sort the array using sort function.
Below is the implementation of the above approach:
C++
// C++ Code for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the array// after performing the operationvector<int> sortedpower(vector<int>& nums, int K){ // Loop is used for performing power of K for (int i = 0; i < nums.size(); i++) { nums[i] = pow(nums[i], K); } // C++ STL function to sort the array // One can use different sorting algorithms sort(nums.begin(), nums.end()); // Returning the vector which is the required answer return nums;}// Driver Codeint main(){ // Defining the vector v vector<int> arr = { -4, -1, 0, 3, 10 }; // Function Call int K = 4; arr = sortedpower(arr, K); for (int i = 0; i < arr.size(); i++) { cout << arr[i] << " "; } cout << endl; return 0;} |
Java
// Java Code for the above approachimport java.io.*;import java.util.*;class GFG { // Function to find the array // after performing the operation public static int[] sortedpower(int nums[], int K) { // Loop is used for performing power of K for (int i = 0; i < nums.length; i++) { nums[i] = (int)Math.pow(nums[i], K); } // Java library function to sort the array // One can use different sorting algorithms Arrays.sort(nums); // Returning the array which is the required answer return nums; } // Driver Code public static void main(String[] args) { // Defining the array v int arr[] = { -4, -1, 0, 3, 10 }; // Function Call int K = 4; arr = sortedpower(arr, K); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); }}// This code is contributed by Rohit Pradhan |
Python3
# Python3 Code for the above approach# Function to find the array# after performing the operationdef sortedpower(nums, K) : # Loop is used for performing power of K for i in range(len(nums)) : nums[i] = pow(nums[i], K); # C++ STL function to sort the array # One can use different sorting algorithms nums.sort(); # Returning the vector which is the required answer return nums;# Driver Codeif __name__ == "__main__" : # Defining the vector v arr = [ -4, -1, 0, 3, 10 ]; # Function Call K = 4; arr = sortedpower(arr, K); for i in range(len(arr)) : print(arr[i],end=" "); print() # This code is contributed by AnkThon |
C#
// C# Code for the above approachusing System;public class GFG { // Function to find the array // after performing the operation public static int[] sortedpower(int[] nums, int K) { // Loop is used for performing power of K for (int i = 0; i < nums.Length; i++) { nums[i] = (int)Math.Pow(nums[i], K); } // Java library function to sort the array // One can use different sorting algorithms Array.Sort(nums); // Returning the array which is the required answer return nums; } static public void Main() { // Code int[] arr = { -4, -1, 0, 3, 10 }; // Function Call int K = 4; arr = sortedpower(arr, K); for (int i = 0; i < arr.Length; i++) { Console.Write(arr[i] + " "); } Console.WriteLine(); }}// This code is contributed by lokeshmvs21 |
Javascript
<script>// Function to find the array// after performing the operationfunction compare(a, b){ return a - b;}function sortedpower(nums, K){ // Loop is used for performing power of K for (let i = 0; i < nums.length; i++) { nums[i] = Math.pow(nums[i], K); } // One can use different sorting algorithms nums.sort(); // Returning the vector which is the required answer return nums;}// Driver Code // Defining the vector v var arr = [ -4, -1, 0, 3, 10 ]; // Function Call let K = 4; arr = sortedpower(arr, K); for (let i = 0; i < arr.length; i++) { document.write(arr[i]+ " "); } document.write( "<br>"); // This code is contributed by satwik4409. </script> |
Output
0 1 81 256 10000
Time Complexity: O(N * logN * logK)
Auxiliary Space: O(1)
Efficient Approach:
Find the element in arr[] greater than equal to 0 say at index i and use two pointers to iterate from i-1 to 0 and i to N-1 compare these elements simultaneously and store them in increasing order of magnitude(absolute value).
Follow the below steps to implement the above approach:
- Firstly find the element which is just greater than or equal to 0.
- If K is odd, we will simply perform power of K operation because the array is already sorted and the after performing Pow operation sign of integers will not change.
- If K is even,
- Then there will be 2 cases.
- Case 1: There is no element greater than or equal to 0 i.e array only has negative numbers, then store all the elements of the array in reverse order in a new array.
- Case 2: If elements that are just greater than or equal to 0 exists
- Initialize two pointers.
- First traverse array from that index upto the final element.
- Second traverse array from that index to the first element.
- While traversing check the absolute values of both the elements simultaneously and store the array in increasing order of absolute values.
- Then there will be 2 cases.
- After getting the new array, perform power of K operation on all the elements of the new array, which is the required answer.
Below is the implementation of the above approach:
C++
// C++ Code for above approach#include <bits/stdc++.h>using namespace std;// Function to find the new arrayvector<int> sortedpower(vector<int>& nums, int K){ // Declaring new vector to store ans vector<int> v; if (K % 2 == 0) { int idx = -1; // Loop to find element which is just greater than or // equal to 0 for (int i = 0; i < nums.size(); i++) { if (nums[i] >= 0) { idx = i; break; } } // If there is no element // which is greater than or equal to 0 if (idx == -1) { for (int i = nums.size() - 1; i >= 0; i--) { v.push_back(nums[i]); } } // If we find that element else { // Making 2 pointers int i = idx - 1; int j = idx; while ((i >= 0) || (j < nums.size())) { // If there no negative number left in the // array if (i == -1) { v.push_back(nums[j]); j++; } // If there no positive number left in the // array else if (j == nums.size()) { v.push_back(nums[i]); i--; } // comparing absolute values of negative // and positive number and arranging them in // increasing order of absolute values else if ((abs(nums[i]) > nums[j])) { v.push_back(nums[j]); j++; } else { v.push_back(nums[i]); i--; } } } } else { v = nums; } // Performing power of 4 operation on all the array // elements for (int i = 0; i < v.size(); i++) { v[i] = pow(v[i], K); } // Returning the required answer return v;}// Driver Codeint main(){ // Defining the vector v vector<int> arr = { -4, -1, 0, 3, 10 }; int K = 4; // Function Call arr = sortedpower(arr, K); for (int i = 0; i < arr.size(); i++) { cout << arr[i] << " "; } return 0;} |
Java
import java.io.*;import java.util.*;class GFG { public static ArrayList<Integer> sortedpower(ArrayList<Integer> nums,int K) { // Declaring new vector to store ans ArrayList<Integer> v = new ArrayList<>(); if (K % 2 == 0) { int idx = -1; // Loop to find element which is just greater than or // equal to 0 for (int i = 0; i < nums.size(); i++) { if (nums.get(i) >= 0) { idx = i; break; } } // If there is no element // which is greater than or equal to 0 if (idx == -1) { for (int i = nums.size() - 1; i >= 0; i--) { v.add(nums.get(i)); } } // If we find that element else { // Making 2 pointers int i = idx - 1; int j = idx; while ((i >= 0) || (j < nums.size())) { // If there no negative number left in the // array if (i == -1) { v.add(nums.get(j)); j++; } // If there no positive number left in the // array else if (j == nums.size()) { v.add(nums.get(i)); i--; } // comparing absolute values of negative // and positive number and arranging them in // increasing order of absolute values else if (((int)Math.abs(nums.get(i)) > nums.get(j))) { v.add(nums.get(j)); j++; } else { v.add(nums.get(i)); i--; } } } } else { v = nums; } // Performing power of 4 operation on all the array // elements for (int i = 0; i < v.size(); i++) { v.set(i,(int)Math.pow(v.get(i), K)); } // Returning the required answer return v; } public static void main(String[] args) { // Defining the vector v ArrayList<Integer> arr = new ArrayList<Integer>( Arrays. asList( -4, -1, 0, 3, 10 ) ); int K = 4; // Function Call arr = sortedpower(arr, K); for (int i = 0; i < arr.size(); i++) { System.out.print(arr.get(i) + " "); } }}// This code is contributed by adityapatil12 |
Python3
# Python code for the above approach# Function to find the new arraydef sortedpower(nums, K): # Declaring new array to store ans v = [] if(K % 2 is 0): idx = -1 # loop to find element which is just greater than equal to 0 for i in range(len(nums)): if(nums[i] >= 0): idx = i break # If there is no element which is greater than or equal to 0 if(idx is -1): for i in range(len(nums)-1, -1, -1): v.append(nums[i]) # If we find that element else: # Making 2 pointers i = idx - 1 j = idx while(i >= 0 or j < len(nums)): # If there no negative number left in the array if(i is -1): v.append(nums[j]) j += 1 # If there no positive number left in the array elif(j is len(nums)): v.append(nums[i]) i -= 1 # Comparing absolute values of negative and positive # number and arranging them increasing order of absolute # values elif(abs(nums[i]) > nums[j]): v.append(nums[j]) j += 1 else: v.append(nums[i]) i -= 1 else: v = nums # performing power of 4 operation on all the array elements for i in range(len(v)): v[i] = pow(v[i], K) # Returning the required answer return varr = [-4, -1, 0, 3, 10]K = 4# Function callarr = sortedpower(arr, K)for i in range(len(arr)): print(arr[i], end=" ")# This code is contributed by lokeshmvs21. |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;public class GFG { // Function to find the required array static int[] sortedpower(int[] nums, int K) { // Creating vector of same size as nums to store the // ans int[] v = new int[(nums.Length)]; int k = 0; if (k % 2 == 0) { int idx = -1; // Loop to find element which is just greater // than or equal to 0 for (int i = 0; i < nums.Length; i++) { if (nums[i] >= 0) { idx = i; break; } } // If there is no element // which is greater than or equal to 0 if (idx == -1) { for (int i = nums.Length - 1; i >= 0; i--) { v[k++] = nums[i]; } } // If we find that element else { // Making 2 pointers int i = idx - 1; int j = idx; while ((i >= 0) || (j < nums.Length)) { // If there no negative number left in // the array if (i == -1) { v[k++] = nums[j]; j++; } // If there no positive number left in // the array else if (j == nums.Length) { v[k++] = nums[i]; i--; } // comparing absolute values of negative // and positive number and arranging // them in increasing order of absolute // values else if ((Math.Abs(nums[i]) > nums[j])) { v[k++] = nums[j]; j++; } else { v[k++] = nums[i]; i--; } } } } else { for (int i = 0; i < nums.Length; i++) { v[k++] = nums[i]; } } // Returning the required answer // Performing power of 4 operation on all the array // elements for (int i = 0; i < v.Length; i++) { v[i] = (int)Math.Pow(v[i], K); } return v; } // Driver Code public static void Main(string[] args) { // Defining the vector v int[] arr = { -4, -1, 0, 3, 10 }; int K = 4; // Function Call arr = sortedpower(arr, K); for (int i = 0; i < arr.Length; i++) { Console.Write(arr[i] + " "); } }}// This code is contributed by garg28harsh. |
Javascript
// Javascript Code for above approach// Function to find the new arrayfunction sortedpower( nums, K){ // Declaring new vector to store ans const v=[]; if (K % 2 == 0) { let idx = -1; // Loop to find element which is just greater than or // equal to 0 for (let i = 0; i < nums.length; i++) { if (nums[i] >= 0) { idx = i; break; } } // If there is no element // which is greater than or equal to 0 if (idx == -1) { for (let i = nums.length - 1; i >= 0; i--) { v.push(nums[i]); } } // If we find that element else { // Making 2 pointers let i = idx - 1; let j = idx; while ((i >= 0) || (j < nums.length)) { // If there no negative number left in the // array if (i == -1) { v.push(nums[j]); j++; } // If there no positive number left in the // array else if (j == nums.length) { v.push(nums[i]); i--; } // comparing absolute values of negative // and positive number and arranging them in // increasing order of absolute values else if ((Math.abs(nums[i]) > nums[j])) { v.push(nums[j]); j++; } else { v.push(nums[i]); i--; } } } } else { for(let i=0;i<nums.length;i++) { v.push(nums[i]); } } // Performing power of 4 operation on all the array // elements for (let i = 0; i < v.length; i++) { v[i] = Math.pow(v[i], K); } // Returning the required answer return v;}// Driver Code // Defining the vector v let arr = [ -4, -1, 0, 3, 10]; let K = 4; // Function Call arr = sortedpower(arr, K); var str = arr.join(' '); document.write(str);// This code is contributed by garg28harsh. |
Output
0 1 81 256 10000
Time Complexity: O(N)
Space Complexity: O(N)
Another Efficient Approach:
Use two pointers left and right pointing towards First and Last index of array then move the pointers towards each other i.e. left towards right and right towards left simultaneously compare the Nth power of the pointed index values and store in increasing order.
Follow the below steps to Implement the Idea:
- Make 2 pointers left and right pointing towards the first and the last elements of array respectively.
- Then calculate the power of K of both the values and compare with each other.
- If the left one is bigger, push it at the last of the answer vector and increment the left pointer.
- If the right one is bigger, push it at the last of ans vector and decrement the right pointer.
Below is the implementation of the above approach:
C++
// C++ Code for above approach#include <bits/stdc++.h>using namespace std;// Function to find the required arrayvector<int> sortedpower(vector<int>& nums, int K){ // Creating vector of same size as nums to store the ans vector<int> v(nums.size()); // Make 2 pointer k and j int k = 0; int j = nums.size() - 1; // Traversing the vector in reverse order for (int i = nums.size() - 1; i >= 0; i--) { // Squaring both the elements int a = pow(nums[k], K); int b = pow(nums[j], K); if (a >= b) { v[i] = a; k++; } else { v[i] = b; j--; } } // Returning the required answer return v;}// Driver Codeint main(){ // Defining the vector v vector<int> arr = { -4, -1, 0, 3, 10 }; int K = 4; // Function Call arr = sortedpower(arr, K); for (int i = 0; i < arr.size(); i++) { cout << arr[i] << " "; } return 0;} |
Java
// Java code to implement the above approachimport java.util.*;class GFG { // Function to find the required array static int[] sortedpower(int[] nums, int K) { // Creating vector of same size as nums to store the ans int[] v = new int[(nums.length)]; // Make 2 pointer k and j int k = 0; int j = nums.length - 1; // Traversing the vector in reverse order for (int i = nums.length - 1; i >= 0; i--) { // Squaring both the elements int a = (int)Math.pow(nums[k], K); int b = (int)Math.pow(nums[j], K); if (a >= b) { v[i] = a; k++; } else { v[i] = b; j--; } } // Returning the required answer return v; } // Driver Code public static void main (String[] args) { // Defining the vector v int[] arr = { -4, -1, 0, 3, 10 }; int K = 4; // Function Call arr = sortedpower(arr, K); for (int i = 0; i < arr.length; i++) { System.out.print( arr[i] + " "); } }}// This code is contributed by sanjoy_62. |
Python3
# Python3 Code for above approach# Function to find the required arraydef sortedpower(nums, K) : # Creating vector of same size as nums to store the ans v = [0] * len(nums); # Make 2 pointer k and j k = 0; j = len(nums) - 1; # Traversing the vector in reverse order for i in range(len(nums) - 1, -1, -1) : # Squaring both the elements a = nums[k] ** K b = nums[j] ** K; if (a >= b) : v[i] = a; k += 1; else : v[i] = b; j -= 1; # Returning the required answer return v;# Driver Codeif __name__ == "__main__" : # Defining the vector v arr = [ -4, -1, 0, 3, 10 ]; K = 4; # Function Call arr = sortedpower(arr, K); for i in range(len(arr)) : print(arr[i], end=" "); # This code is contributed by AnkThon |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;public class GFG { // Function to find the required array static int[] sortedpower(int[] nums, int K) { // Creating vector of same size as nums to store the ans int[] v = new int[(nums.Length)]; // Make 2 pointer k and j int k = 0; int j = nums.Length - 1; // Traversing the vector in reverse order for (int i = nums.Length - 1; i >= 0; i--) { // Squaring both the elements int a = (int)Math.Pow(nums[k], K); int b = (int)Math.Pow(nums[j], K); if (a >= b) { v[i] = a; k++; } else { v[i] = b; j--; } } // Returning the required answer return v; } // Driver Code public static void Main(string[] args) { // Defining the vector v int[] arr = { -4, -1, 0, 3, 10 }; int K = 4; // Function Call arr = sortedpower(arr, K); for (int i = 0; i < arr.Length; i++) { Console.Write( arr[i] + " "); } }}// This code is contributed by code_hunt. |
Javascript
<script>// Javascript Code for the above approach// Function to find the required arrayfunction sortedpower(nums, K){ // Creating vector of same size as nums to store the ans let v = new Array(nums.length); // Make 2 pointer k and j let k = 0; let j = nums.length - 1; // Traversing the vector in reverse order for (let i = nums.length - 1; i >= 0; i--) { // Squaring both the elements let a = Math.pow(nums[k], K); let b = Math.pow(nums[j], K); if (a >= b) { v[i] = a; k++; } else { v[i] = b; j--; } } // Returning the required answer return v;}// Driver Code // Defining the vector v let arr = [ -4, -1, 0, 3, 10 ]; // Function Call let K = 4; arr = sortedpower(arr, K); for (let i = 0; i < arr.length; i++) { document.write(arr[i]+ " "); } document.write( "<br>"); // This code is contributed by satwik4409. </script> |
Output
0 1 81 256 10000
Time Complexity: O(N)
Space Complexity: O(N)
Share your thoughts in the comments
