Given an array arr[] of N distinct integers, the task is to replace every element by smallest among all other remaining elements of the array.
Examples:
Input: arr[] = { 4, 2, 1, 3 }
Output: arr[]= { 1, 1, 2, 1 }
Explanation:
For arr[0], the smallest out of the remaining elements is 1. So arr[0] is replaced by 1.
For arr[1], the smallest out of the remaining elements is 1. So arr[1] is replaced by 1.
For arr[2], the smallest out of the remaining elements is 2. So arr[2] is replaced by 2.
For arr[3], the smallest out of the remaining elements is 1. So arr[3] is replaced by 1.
Input: arr[] = { 1, 5, 2, 4 }
Output: arr[] = { 2, 1, 1, 1 }
Naive Approach:
Run a nested loop and find the smallest of all other elements for every single element and store them.
Time Complexity: O(N2)
Efficient Approach:
- Traverse the array and find the two smallest elements of the array.
- Traverse the array again, now replace the smallest element with the second smallest element and replace every other element in the array with the smallest element.
- Print the modified array.
Below is the implementation of above approach:
C++
// C# implementation to find the // maximum array sum by concatenating // corresponding elements of given two arrays using System;class GFG{// Function to join the two numbers static int joinNumbers(int numA, int numB){ int revB = 0; // Loop to reverse the digits // of the one number while (numB > 0) { revB = revB * 10 + (numB % 10); numB = numB / 10; } // Loop to join two numbers while (revB > 0) { numA = numA * 10 + (revB % 10); revB = revB / 10; } return numA;}// Function to find the maximum array sum static int findMaxSum(int []A, int []B, int n){ int []maxArr = new int[n]; // Loop to iterate over the two // elements of the array for(int i = 0; i < n; ++i) { int X = joinNumbers(A[i], B[i]); int Y = joinNumbers(B[i], A[i]); int mx = Math.Max(X, Y); maxArr[i] = mx; } // Find the array sum int maxAns = 0; for(int i = 0; i < n; i++) { maxAns += maxArr[i]; } // Return the array sum return maxAns;}// Driver Codepublic static void Main(String []args){ int N = 5; int []A = { 11, 23, 38, 43, 59 }; int []B = { 36, 24, 17, 40, 56 }; Console.WriteLine(findMaxSum(A, B, N));}}// This code is contributed by Rajput-Ji |
Java
// Java code for the above approach.import java.util.*;class GFG { static void ReplaceElements( int[] arr, int n) { // There should be atleast // two elements if (n < 2) { System.out.println( "Invalid Input"); return; } int firstSmallest = Integer.MAX_VALUE; int secondSmallest = Integer.MAX_VALUE; for (int i = 0; i < n; i++) { // If current element is smaller // than firstSmallest then update // both firstSmallest // and secondSmallest if (arr[i] < firstSmallest) { secondSmallest = firstSmallest; firstSmallest = arr[i]; } // If arr[i] is in between // firstSmallest and secondSmallest // then update secondSmallest else if (arr[i] < secondSmallest && arr[i] != firstSmallest) secondSmallest = arr[i]; } // Replace every element by // smallest of all other elements for (int i = 0; i < n; i++) { if (arr[i] != firstSmallest) arr[i] = firstSmallest; else arr[i] = secondSmallest; } // Print the modified array. for (int i = 0; i < n; ++i) { System.out.print(arr[i] + ", "); } } // Driver code public static void main( String[] args) { int arr[] = { 4, 2, 1, 3 }; int n = arr.length; ReplaceElements(arr, n); }} |
Python3
# Python3 code for the above approach.def ReplaceElements(arr, n): # There should be atleast # two elements if (n < 2): print("Invalid Input") return firstSmallest = 10 ** 18 secondSmallest = 10 ** 18 for i in range(n): # If current element is smaller # than firstSmallest then update # both firstSmallest # and secondSmallest if (arr[i] < firstSmallest): secondSmallest = firstSmallest firstSmallest = arr[i] # If arr[i] is in between # firstSmallest and secondSmallest # then update secondSmallest elif (arr[i] < secondSmallest and arr[i] != firstSmallest): secondSmallest = arr[i] # Replace every element by # smallest of all other elements for i in range(n): if (arr[i] != firstSmallest): arr[i] = firstSmallest else: arr[i] = secondSmallest # Print the modified array. for i in arr: print(i, end = ", ")# Driver codeif __name__ == '__main__': arr= [ 4, 2, 1, 3 ] n = len(arr) ReplaceElements(arr, n)# This code is contributed by mohit kumar 29 |
C#
// C# code for the above approach.using System;class GFG{static void ReplaceElements(int[] arr, int n){ // There should be atleast // two elements if (n < 2) { Console.Write("Invalid Input"); return; } int firstSmallest = Int32.MaxValue; int secondSmallest = Int32.MaxValue; for(int i = 0; i < n; i++) { // If current element is smaller // than firstSmallest then update // both firstSmallest // and secondSmallest if (arr[i] < firstSmallest) { secondSmallest = firstSmallest; firstSmallest = arr[i]; } // If arr[i] is in between // firstSmallest and secondSmallest // then update secondSmallest else if (arr[i] < secondSmallest && arr[i] != firstSmallest) secondSmallest = arr[i]; } // Replace every element by // smallest of all other elements for(int i = 0; i < n; i++) { if (arr[i] != firstSmallest) arr[i] = firstSmallest; else arr[i] = secondSmallest; } // Print the modified array. for(int i = 0; i < n; ++i) { Console.Write(arr[i] + ", "); }}// Driver codepublic static void Main(){ int []arr = { 4, 2, 1, 3 }; int n = arr.Length; ReplaceElements(arr, n);}}// This code is contributed by Nidhi_Biet |
Javascript
<script>// Javascript code for the above approach.function ReplaceElements(arr, n){ // There should be atleast // two elements if (n < 2) { document.write( "Invalid Input<br>"); return; } let firstSmallest = Number.MAX_VALUE; let secondSmallest = Number.MAX_VALUE; for (let i = 0; i < n; i++) { // If current element is smaller // than firstSmallest then update // both firstSmallest // and secondSmallest if (arr[i] < firstSmallest) { secondSmallest = firstSmallest; firstSmallest = arr[i]; } // If arr[i] is in between // firstSmallest and secondSmallest // then update secondSmallest else if (arr[i] < secondSmallest && arr[i] != firstSmallest) secondSmallest = arr[i]; } // Replace every element by // smallest of all other elements for (let i = 0; i < n; i++) { if (arr[i] != firstSmallest) arr[i] = firstSmallest; else arr[i] = secondSmallest; } // Print the modified array. for (let i = 0; i < n; ++i) { document.write(arr[i] + ", "); }} // Driver codelet arr=[ 4, 2, 1, 3 ];let n = arr.length;ReplaceElements(arr, n); // This code is contributed by unknown2108.</script> |
Output:
1, 1, 2, 1,
Time Complexity: O(N)
Space Complexity: 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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
