Sort an Array which contains 1 to n values using Mathematical Formula

Given an array arr[] of size n, having distinct integers from 1 to n, the task is to sort the array.

Input: arr[] = { 2, 1, 5, 4, 3} 
Output: {1, 2, 3, 4, 5}

Input: arr[] = {1, 2, 3, 4, 5, 6} 
Output: {1, 2, 3, 4, 5, 6} 

We have already discussed different approaches to solve the problem in the post Sort an array which contains 1 to n values. In this post, we will discuss a mathematical approach to sort the array.

Using Mathematical Formula – O(n) Time and O(1) Space

The idea is to traverse the input array and for each element arr[i], place it at its correct index, that is (arr[i] – 1). The problem with this approach is that if we update arr[arr[i] – 1] with arr[i] we will end up overwriting the element at index (arr[i] – 1). To solve this problem, we can find the maximum value in the array, that is (n + 1) and use it to store the original as well as the updated value at each index.

Let’s say for any index i, we have the current element as arr[i]. We know that the correct index for arr[i], say correctIdx is (arr[i] – 1). Now, instead of overwriting arr[correctIdx], we add (arr[i] * (n + 1)) to arr[correctIdx]. This is because we can get the original value by arr[i] % (n + 1) and updated value by arr[i] / (n + 1).

After traversing the array and modifying each index, traverse again and update arr[i] to arr[i] / (n + 1) to get the sorted values.

// C++ Program to sort distinct integer array from 
// 1 to n using Mathematical formula 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// function to sort the array
void sortArr(vector<int> &arr) {
    int n = arr.size();
    
    for(int i = 0; i < n; i++) {
       int originalVal = arr[i] % (n + 1);
       int correctIdx = originalVal - 1;
       arr[correctIdx] += originalVal * (n + 1);
    }
  
    for(int i = 0; i < n; i++) 
        arr[i] = arr[i] / (n + 1);
  
}

int main() {
    vector<int> arr = { 2, 1, 5, 4, 3 };
    sortArr(arr);  
    for(int i = 0; i < arr.size(); i++)
        cout << arr[i] << " ";
  
    return 0;
}

// C Program to sort distinct integer array from 
// 1 to n using Mathematical formula 

#include <stdio.h>

// function to sort the array
void sortArr(int *arr, int n) {  
    for (int i = 0; i < n; i++) {
        int originalVal = arr[i] % (n + 1);
        int correctIdx = originalVal - 1;
        arr[correctIdx] += originalVal * (n + 1);
    }
  
    for (int i = 0; i < n; i++) {
        arr[i] = arr[i] / (n + 1);
    }
}

int main() {
    int arr[] = { 2, 1, 5, 4, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
    sortArr(arr, n);  
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
  
    return 0;
}

// Java Program to sort distinct integer array from 
// 1 to n using Mathematical formula 

import java.util.Arrays;

class GfG {

    // function to sort the array
    static void sortArr(int[] arr) {
        int n = arr.length;
      
        for (int i = 0; i < n; i++) {
            int originalVal = arr[i] % (n + 1);
            int correctIdx = originalVal - 1;
            arr[correctIdx] += originalVal * (n + 1);
        }

        for (int i = 0; i < n; i++)
            arr[i] = arr[i] / (n + 1);
    }

    public static void main(String[] args) {
        int[] arr = { 2, 1, 5, 4, 3 };
        sortArr(arr);  
        for (int i = 0; i < arr.length; i++)
            System.out.print(arr[i] + " ");
    }
}

# Python Program to sort distinct integer array from 
# 1 to n using Mathematical formula 

def sortArr(arr):
    n = len(arr)
    
    for i in range(n):
        originalVal = arr[i] % (n + 1)
        correctIdx = originalVal - 1
        arr[correctIdx] += originalVal * (n + 1)
    
    for i in range(n):
        arr[i] = arr[i] // (n + 1)

if __name__ == "__main__":
    arr = [2, 1, 5, 4, 3]
    sortArr(arr)  
    for i in range(len(arr)):
        print(arr[i], end=" ")

// C# Program to sort distinct integer array from 
// 1 to n using Mathematical formula 

using System;

class GfG {
  
    // function to sort the array
    static void sortArr(int[] arr) {
        int n = arr.Length;
        for (int i = 0; i < n; i++) {
            int originalVal = arr[i] % (n + 1);
            int correctIdx = originalVal - 1;
            arr[correctIdx] += originalVal * (n + 1);
        }

        for (int i = 0; i < n; i++)
            arr[i] = arr[i] / (n + 1);
    }

    static void Main() {
        int[] arr = { 2, 1, 5, 4, 3 };
        sortArr(arr);
        for (int i = 0; i < arr.Length; i++) {
            Console.Write(arr[i] + " ");
        }
    }
}

// JavaScript Program to sort distinct integer array from 
// 1 to n using Mathematical formula 

function sortArr(arr) {
    let n = arr.length;
    
    for (let i = 0; i < n; i++) {
        let originalVal = arr[i] % (n + 1);
        let correctIdx = originalVal - 1;
        arr[correctIdx] += originalVal * (n + 1);
    }
  
    for (let i = 0; i < n; i++)
        arr[i] = Math.floor(arr[i] / (n + 1));
}

let arr = [2, 1, 5, 4, 3];
sortArr(arr);  
console.log(arr.join(" "));

1 2 3 4 5 

coder001

Follow

Improve

Article Tags :

• Algorithms
• Arrays
• DSA
• Sorting
• Natural Numbers

+1 More

Practice Tags :

• Algorithms
• Arrays
• Sorting