Rearrange an array to maximize i*arr[i]
Last Updated :
07 Sep, 2022
Given an array of N integers, you have to select all of these integers in any order. For every integer you select, you get points equal to the value of: the selected integer * number of integers selected before the current integer. Your task is to maximize these points.
Note: You can select every integer exactly 1 time.
Examples:
Input: a = {1, 4, 2, 3, 9}
Output: 56
The optimal solution for this array would be select the numbers in the order 1, 2, 3, 4, 9 that gives points 0, 2, 6, 12, 36 respectively and giving a total maximum points of 56.
Input: a = {1, 2, 2, 4, 9}
Output: 54
The optimal solution for this array would be select the numbers in the order 1, 2, 2, 4, 9 that gives points 0, 2, 4, 12, 36 respectively and giving a total maximum points of 54.
The idea is to use Greedy Approach, i.e., maximize the multiplier for the largest element. We sort the given array and start picking elements in this sorted manner, starting with the first element.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
static int findOptimalSolution(int a[], int N)
{
sort(a, a+N);
int points = 0;
for (int i = 0; i < N; i++) {
points += a[i] * i;
}
return points;
}
int main() {
int a[] = { 1, 4, 2, 3, 9 };
int N = sizeof(a)/sizeof(a[0]);
cout<<(findOptimalSolution(a, N));
return 0;
}
|
Java
import java.io.*;
import java.util.*;
class GFG {
static int findOptimalSolution(int[] a, int N)
{
Arrays.sort(a);
int points = 0;
for (int i = 0; i < N; i++) {
points += a[i] * i;
}
return points;
}
public static void main(String args[])
{
int[] a = { 1, 4, 2, 3, 9 };
int N = a.length;
System.out.println(findOptimalSolution(a, N));
}
}
|
Python3
def findOptimalSolution(a, N) :
a.sort()
points = 0
for i in range(0, N):
points += a[i] * i
return points
if __name__ == "__main__":
a = [1, 4, 2, 3, 9]
N = len(a)
print(findOptimalSolution(a, N))
|
C#
using System;
public class GFG{
static int findOptimalSolution(int[]a, int N)
{
Array.Sort(a);
int points = 0;
for (int i = 0; i < N; i++) {
points += a[i] * i;
}
return points;
}
static public void Main (){
int[] a = { 1, 4, 2, 3, 9 };
int N = a.Length;
Console.WriteLine(findOptimalSolution(a, N));
}
}
|
PHP
<?php
function findOptimalSolution($a, $N)
{
sort($a);
$points = 0;
for ($i = 0; $i < $N; $i++)
{
$points += $a[$i] * $i;
}
return $points;
}
$a = array( 1, 4, 2, 3, 9 );
$N = sizeof($a);
echo (findOptimalSolution($a, $N));
?>
|
Javascript
<script>
function findOptimalSolution(a, N)
{
a.sort(function(a, b){return a - b});
let points = 0;
for (let i = 0; i < N; i++) {
points += a[i] * i;
}
return points;
}
let a = [ 1, 4, 2, 3, 9 ];
let N = a.length;
document.write(findOptimalSolution(a, N));
</script>
|
Complexity analysis:
- Time Complexity: O(n log(n))
- Auxiliary Space: O(1)