Tutorialspoint.dev

Sort an array after applying the given equation

We have an integer array that is sorted in ascending order. We also have 3 integers A, B and C. We need to apply A*x*x + B*x + C for each element x in the array and sort the modified array.
Example:

Input : arr[] = {-1, 0, 1, 2, 3, 4} 
       A = -1, B = 2, C = -1
Output : {-9, -4, -4, -1, -1, 0}
Input array is {-1, 0, 1, 2, 3, 4}. After
applying the equation A*x*x + B*x + C on
every element x we get, {-4,-1, 0, -1, -4, -9}
After sorting, we get {-9, -4, -4, -1, -1, 0}

Asked in : Adobe


Method 1 (Simple) :

1- Apply the given equation on all the elements. O(n)
2- Sort the modified array. O(n Log n)



Time complexity of O(n log n)

Method 2(Efficient): Parabolic Property

The equation given is parabolic. So the result of applying it to a sorted array will result in an array that will have a maximum/minimum with the sub-arrays to its left and right sorted.

In the above example, maximum is 0 and the sub array to its left {-4, -1} is sorted in ascending order and the sub-array to its right {-1, -4, -9} is sorted in descending order.
All we need to do is merge these sorted arrays which is linear in time.

So the algorithm is:

  1. Apply equation on each element.
  2. Find maximum/minimum.
  3. Merge sub-arrays.

Note : The below code assumes that the modified array is first increasing then decreasing.

C++

// C program to sort an array after applying equation
// A*x*x + B*x + C
#include<bits/stdc++.h>
using namespace std;
  
// Function to sort an array after applying given
// equation.
void sortArray(int arr[], int n, int A, int B, int C)
{
   // Apply equation on all elements
    for (int i = 0; i < n; i++)
        arr[i] = A*arr[i]*arr[i] + B*arr[i] + C;
  
    // Find maximum element in resultant array
    int index, maximum = INT_MIN;
    for (int i = 0; i< n; i++)
    {
        if (maximum < arr[i])
        {
            index = i;
            maximum = arr[i];
        }
    }
  
    // Use maximum element as a break point
    // and merge both subarrays usin simple
    // merge function of merge sort
    int i = 0, j = n-1;
    int new_arr[n], k = 0;
    while (i < index && j > index)
    {
        if (arr[i] < arr[j])
            new_arr[k++] = arr[i++];
        else
            new_arr[k++] = arr[j--];
    }
  
    // Merge remaining elements
    while (i < index)
        new_arr[k++] = arr[i++];
    while (j > index)
        new_arr[k++] = arr[j--];
  
    new_arr[n-1] = maximum;
  
    // Modify original array
    for (int i = 0; i < n ; i++)
        arr[i] = new_arr[i];
}
  
// Driver code
int main()
{
    int arr[] = {-21 ,-15, 12, 13, 14 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int A = -6, B =-7, C = 2;
  
    sortArray(arr, n, A, B, C);
  
    cout << "Array after sorting is : n";
    for (int i=0; i<n; i++)
       cout << arr[i] << " ";
  
    return 0;
}

Java

// Java program to sort an array after applying equation
// A*x*x + B*x + C
  
class Main
{
    // Function to sort an array after applying given
    // equation.
    static void sortArray(int arr[], int n, int A, int B, int C)
    {
       // Apply equation on all elements
        for (int i = 0; i < n; i++)
            arr[i] = A*arr[i]*arr[i] + B*arr[i] + C;
       
        // Find maximum element in resultant array
        int index=-1;
        int maximum = -999999;
        for (int i = 0; i< n; i++)
        {
            if (maximum < arr[i])
            {
                index = i;
                maximum = arr[i];
            }
        }
       
        // Use maximum element as a break point
        // and merge both subarrays usin simple
        // merge function of merge sort
        int i = 0, j = n-1;
        int[] new_arr = new int[n];
        int k = 0;
        while (i < index && j > index)
        {
            if (arr[i] < arr[j])
                new_arr[k++] = arr[i++];
            else
                new_arr[k++] = arr[j--];
        }
       
        // Merge remaining elements
        while (i < index)
            new_arr[k++] = arr[i++];
        while (j > index)
            new_arr[k++] = arr[j--];
       
        new_arr[n-1] = maximum;
       
        // Modify original array
        for (int p = 0; p < n ; p++)
            arr[p] = new_arr[p];
    }
      
    // main function
    public static void main (String[] args) 
    {
        int arr[] = {-21 ,-15, 12, 13, 14 };
        int n = arr.length;
        int A = -6, B =-7, C = 2;
       
        sortArray(arr, n, A, B, C);
       
        System.out.println("Array after sorting is : ");
        for (int i=0; i<n; i++)
           System.out.print(arr[i]+" ");
    }
}
  
/* This code is contributed by Harsh Agarwal */

Python3

# Python3 program to sort an 
# array after applying equation 
# A*x*x + B*x + C 
import sys
  
# Function to sort an array 
# after applying given equation. 
def sortArray(arr, n, A, B, C):
  
    # Apply equation on all elements 
    for i in range(n):
        arr[i] = (A * arr[i] * arr[i] + 
                  B * arr[i] + C)
    index = -(sys.maxsize - 1)
    maximum = -(sys.maxsize - 1)
      
    # Find maximum element in
    # resultant array
    for i in range(n):
        if maximum < arr[i]:
            index = i
            maximum = arr[i]
      
    # Use maximum element as a break point 
    # and merge both subarrays usin simple 
    # merge function of merge sort 
    i = 0; j = n - 1;
    new_arr = [0] * n
    k = 0
    while i < index and j > index:
        if arr[i] < arr[j]:
            new_arr[k] = arr[i]
            k += 1
            i += 1
        else:
            new_arr[k] = arr[j]
            k += 1
            j -= 1
  
    # Merge remaining elements 
    while i < index:
        new_arr[k] = arr[i]
        k += 1
        i += 1
  
    # Modify original array 
    while j > index:
        new_arr[k] = arr[j]
        k += 1
        j -= 1
        new_arr[n - 1] = maximum 
  
    for i in range(n):
        arr[i] = new_arr[i]
  
# Driver code
arr = [-21, -15, 12, 13, 14]
n = len(arr)
A = -6
B= -7
C = 2
sortArray(arr, n, A, B, C)
print("Array after sorting is:")
for i in range(n):
    print(arr[i], end = " ")
  
# This code is contributed 
# by Shrikant13

C#

// C# program to sort an array after applying equation 
// A*x*x + B*x + C 
   
using System; 
class MAIN 
    // Function to sort an array after applying given 
    // equation. 
    static void sortArray(int[] arr, int n, int A, int B, int C) 
    
       // Apply equation on all elements 
        for (int i = 0; i < n; i++) 
            arr[i] = A*arr[i]*arr[i] + B*arr[i] + C; 
         
        // Find maximum element in resultant array 
        int index=-1; 
        int maximum = -999999; 
        for (int i = 0; i< n; i++) 
        
            if (maximum < arr[i]) 
            
                index = i; 
                maximum = arr[i]; 
            
        
         
        // Use maximum element as a break point 
        // and merge both subarrays usin simple 
        // merge function of merge sort 
        int l = 0, j = n-1; 
        int[] new_arr = new int[n]; 
        int k = 0; 
        while (l < index && j > index) 
        
            if (arr[l] < arr[j]) 
                new_arr[k++] = arr[l++]; 
            else
                new_arr[k++] = arr[j--]; 
        
         
        // Merge remaining elements 
        while (l < index) 
            new_arr[k++] = arr[l++]; 
        while (j > index) 
            new_arr[k++] = arr[j--]; 
         
        new_arr[n-1] = maximum; 
         
        // Modify original array 
        for (int p = 0; p < n ; p++) 
            arr[p] = new_arr[p]; 
    
        
    // main function 
    public static void Main ()  
    
        int[] arr = {-21 ,-15, 12, 13, 14 }; 
        int n = arr.Length; 
        int A = -6, B =-7, C = 2; 
         
        sortArray(arr, n, A, B, C); 
         
        Console.Write("Array after sorting is : "+" "); 
        for (int i=0; i<n; i++) 
           Console.Write(arr[i]+" "); 
    

PHP

<?php
// PHP program to sort an array after 
// applying equation A*x*x + B*x + C
  
// Function to sort an array after 
// applying given   equation.
function sortArray(&$arr, $n, $A, $B, $C)
{
      
    // Apply equation on all elements
    for ($i = 0; $i < $n; $i++)
        $arr[$i] = $A * $arr[$i] * $arr[$i] +
                   $B * $arr[$i] + $C;
  
    // Find maximum element in 
    // resultant array
    $index = 0; 
    $maximum = PHP_INT_MIN;
    for ($i = 0; $i < $n; $i++)
    {
        if ($maximum < $arr[$i])
        {
            $index = $i;
            $maximum = $arr[$i];
        }
    }
  
    // Use maximum element as a break point
    // and merge both subarrays usin simple
    // merge function of merge sort
    $i = 0;
    $j = $n - 1;
    $new_arr = array();
    while ($i < $index && $j > $index)
    {
        if ($arr[$i] < $arr[$j])
            array_push($new_arr, $arr[$i++]);
        else
            array_push($new_arr, $arr[$j--]);
    }
  
    // Merge remaining elements
    while ($i < $index)
        array_push($new_arr, $arr[$i++]);
    while ($j > $index)
        array_push($new_arr, $arr[$j--]);
  
    array_push($new_arr, $maximum);
  
    // Modify original array
    for ($i = 0; $i < count($new_arr) ; $i++)
        $arr[$i] = $new_arr[$i];
}
  
// Driver code
$arr = array(-21 ,-15, 12, 13, 14 );
$n = count($arr);
$A = -6;
$B = -7;
$C = 2;
  
sortArray($arr, $n, $A, $B, $C);
  
echo "Array after sorting is : ";
for ($i = 0; $i < $n; $i++)
    echo $arr[$i] . " ";
  
// This code is contributed by mits
?>


Output:

Array after sorting is : 
-2497 -1272 -1243 -1103 -946 

Time Complexity: O(n)
Auxiliary Space: O(n)

Reference:
http://stackoverflow.com/questions/4551599/sorting-result-array

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter