Rearrange given Array such that each elements is not equal to mean of adjacent elements

0 0 4 minutes read

Given an array arr consisting of N unique integers, the task is to rearrange the array such that element at index i of array should not be mean of adjacent elements (i.e., of index i-1 and i+1). Any possible rearrangement can be returned.

Example:

Input: arr = [5, 4, 3, 2, 1]Output: [5, 3, 4, 2, 1]Explanation: In the input array:
Mean(5, 3) = (5 + 3)/2 = 4,
Mean(4, 2) = (4+ 2 )/2 = 3,
Mean(3, 1) = (3 + 1)/2 = 2.
After rearranging the array as [5, 3, 4, 2, 1], now no element is the mean of adjacent elements: (5 + 4)/2 ? 3, (3 + 2)/2 ? 4, (4 + 1)/2 ? 2

Input: arr = [6, 9, 12, 25, 50 75]Output: [6, 12, 9, 25, 50, 75 ]

Approach: The main observation to solve this problem is that for 3 numbers a, b, and c to satisfy the condition that b shouldn’t be the mean of a and c, [a, b, c] mustn’t be sorted. Therefore, this problem can be solved by following steps:

Iterate over the array from 1 to (N-1)
Check whether (arr[i – 1] + arr[i + 1]) / 2 == arr[i])
If the condition is satisfied swap the elements arr[i] and arr[i+1]

Below is the implementation of the above approach:

C++

// C++ code for above implementation
#include <bits/stdc++.h>
using namespace std;
 
// Function to rearrange the array
void Rearrange(int arr[], int N)
{
 
    // Iterating for array
    for (int i = 1; i < (N - 1); i++) {
 
        // Checking whether the element i
        // is mean of i-1 and i+1
        if ((arr[i - 1] + arr[i + 1]) / 2 == arr[i]) {
 
            // Rearrange by swapping arr[i] and arr[i+1]
            swap(arr[i], arr[i + 1]);
        }
    }
 
    // Printing the output array
    for (int i = 0; i < N; i++) {
        cout << arr[i] << " ";
    }
}
 
 
// Driver code
int main()
{
    int arr[] = { 6, 9, 12, 25, 50, 75 };
    int N = sizeof(arr) / sizeof(int);
 
    // calling the function
    Rearrange(arr, N);
    return 0;
}

Java

// Java program for the above approach
 
import java.io.*;
 
class GFG {
  // Function to rearrange the array
   
static void Rearrange(int arr[], int N)
{
   
    // Iterating for array
    for (int i = 1; i < (N - 1); i++) {
   
        // Checking whether the element i
        // is mean of i-1 and i+1
        if ((arr[i - 1] + arr[i + 1]) / 2 == arr[i]) {
   
            // Rearrange by swapping arr[i] and arr[i+1]
            
          int temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
        }
    }
   
    // Printing the output array
    for (int i = 0; i < N; i++) {
         System.out.print(arr[i] +" ");
    }
}
   
// Driver code
    public static void main (String[] args) {
      int arr[] = { 6, 9, 12, 25, 50, 75 };
    int N = arr.length;
   
    // calling the function
    Rearrange(arr, N);
    }
}
// This code is contributed by Potta Lokesh

C#

// C# program for the above approach

using System;

class GFG {
// Function to rearrange the array

static void Rearrange(int []arr, int N)
{

// Iterating for array
for (int i = 1; i < (N – 1); i++) {

// Checking whether the element i
// is mean of i-1 and i+1
if ((arr[i – 1] + arr[i + 1]) / 2 == arr[i]) {

// Rearrange by swapping arr[i] and arr[i+1]

int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}

// Printing the output array
for (int i = 0; i < N; i++) {
Console.Write(arr[i] +” “);
}
}

// Driver code
public static void Main (String[] args)
{
int []arr = { 6, 9, 12, 25, 50, 75 };
int N = arr.Length;

// calling the function
Rearrange(arr, N);
}
}
// This code is contributed by shivanisinghss2110

Python3

# Python3 program for the above approach
 
# Function to rearrange the array
def Rearrange(arr, N) :
 
    # Iterating for array
    for i in range(1, N - 1) :
 
        # Checking whether the element i
        # is mean of i-1 and i+1
        if ((arr[i - 1] + arr[i + 1]) // 2 == arr[i]) :
 
            # Rearrange by swapping arr[i] and arr[i+1]
            arr[i], arr[i + 1] = arr[i + 1], arr[i];
 
    # Printing the output array
    for i in range(N) :
        print(arr[i],end= " " )
   
 
 
# Driver code
if __name__ == "__main__" :
 
    arr = [ 6, 9, 12, 25, 50, 75 ];
    N = len(arr);
 
    # calling the function
    Rearrange(arr, N);
     
    # This code is contributed by AnkThon

Javascript

<script>
// JavaScript program for the above approach
// Function to rearrange the array
 
function Rearrange(arr, N)
{
 
    // Iterating for array
    for (var i = 1; i < (N - 1); i++) {
 
        // Checking whether the element i
        // is mean of i-1 and i+1
        if ((arr[i - 1] + arr[i + 1]) / 2 == arr[i]) {
 
            // Rearrange by swapping arr[i] and arr[i+1]
             
        var temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
        }
    }
 
    // Printing the output array
    for (var i = 0; i < N; i++) {
        document.write(arr[i] +" ");
    }
}
 
// Driver code
var arr = [ 6, 9, 12, 25, 50, 75 ];
var N = arr.length;
 
// calling the function
Rearrange(arr, N);
     
// This code is contributed by shivanisinghss2110
 
</script>

Output

6 12 9 25 75 50

Time Complexity: O(N)
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!