Given an array of N integers. The task is to find the lexicographically smallest array possible by applying the given operation any number of times. The operation is to pick two elements ai and aj (1<=i, j<=N) such that ai + aj is odd, and then swap ai and aj.
Examples:
Input : a[] = {1, 5, 4, 3, 2}
Output : 1 2 3 4 5
Explanation : First swap (5, 2) and then (4, 3). This is the
lexicographically smallest possible array that can be obtained by
swapping array elements satisfies given condition
Input : a[] = {4, 2}
Output : 4 2
Explanation : Not possible to swap any elements.
Approach: Observe that swapping of 2 elements is possible if they have different parity. If all elements in the array have the same parity (odd + odd and even + even is not odd), no swaps are possible. Hence the answer will be the input array only. Otherwise, you can actually swap any pair of elements. Assume you want to swap 2 elements, a and b, and they have the same parity. There must be a third element c that has a different parity. Without loss of generality, assume the array is [a, b, c]. Let’s do the following swaps:
- Swap a and c:
- Swap b and c: [b, c, a]
- Swap a and c: [b, a, c]
In other words, use c as an intermediate element to swap a and b, and it’ll always return to its original position afterward. Since swapping is possible between any pair of elements, we can always sort the array, which will be the lexicographically smallest array.
Below is the implementation of the above approach:
C++
// CPP program to find possible // lexicographically smaller array// by swapping only elements whose sum is odd #include <bits/stdc++.h>using namespace std;// Function to find possible lexicographically smaller arrayvoid lexicographically_smaller(int arr[], int n){ // To store number of even and odd integers int odd = 0, even = 0; // Find number of even and odd integers for (int i = 0; i < n; i++) { if (arr[i] % 2) odd++; else even++; } // If it possible to make // lexicographically smaller if (odd && even) sort(arr, arr + n); // Print the array for (int i = 0; i < n; i++) cout << arr[i] << " ";}// Driver codeint main(){ int arr[] = { 1, 5, 4, 3, 2 }; int n = sizeof(arr) / sizeof(arr[0]); // Function call lexicographically_smaller(arr, n); return 0;} |
Java
// Java program to find possible // lexicographically smaller array// by swapping only elements whose sum is odd import java.util.*;class GFG {// Function to find possible lexicographically smaller arraystatic void lexicographically_smaller(int arr[], int n){ // To store number of even and odd integers int odd = 0, even = 0; // Find number of even and odd integers for (int i = 0; i < n; i++) { if (arr[i] % 2 == 1) odd++; else even++; } // If it possible to make // lexicographically smaller if (odd > 0 && even > 0) Arrays.sort(arr); // Print the array for (int i = 0; i < n; i++) System.out.print(arr[i] + " ");}// Driver codepublic static void main(String[] args){ int arr[] = { 1, 5, 4, 3, 2 }; int n = arr.length; // Function call lexicographically_smaller(arr, n);}}// This code is contributed by Rajput-Ji |
Python3
# Python3 program to find possible # lexicographically smaller array# by swapping only elements whose sum is odd # Function to find possible # lexicographically smaller arraydef lexicographically_smaller(arr, n): # To store number of even and odd integers odd, even = 0, 0; # Find number of even and odd integers for i in range(n): if (arr[i] % 2 == 1): odd += 1; else: even += 1; # If it possible to make # lexicographically smaller if (odd > 0 and even > 0): arr.sort(); # Print the array for i in range(n): print(arr[i], end = " ");# Driver codeif __name__ == '__main__': arr = [ 1, 5, 4, 3, 2 ]; n = len(arr); # Function call lexicographically_smaller(arr, n);# This code contributed by Rajput-Ji |
C#
// C# program to find possible // lexicographically smaller array by// swapping only elements whose sum is odd using System; class GFG {// Function to find possible // lexicographically smaller arraystatic void lexicographically_smaller(int []arr, int n){ // To store number of even and odd integers int odd = 0, even = 0; // Find number of even and odd integers for (int i = 0; i < n; i++) { if (arr[i] % 2 == 1) odd++; else even++; } // If it possible to make // lexicographically smaller if (odd > 0 && even > 0) Array.Sort(arr); // Print the array for (int i = 0; i < n; i++) Console.Write(arr[i] + " ");}// Driver codepublic static void Main(String[] args){ int []arr = { 1, 5, 4, 3, 2 }; int n = arr.Length; // Function call lexicographically_smaller(arr, n);}}// This code is contributed by 29AjayKumar |
Javascript
<script>// javascript program to find possible // lexicographically smaller array// by swapping only elements whose sum is odd // Function to find possible lexicographically smaller arrayfunction lexicographically_smaller(arr , n){ // To store number of even and odd integers var odd = 0, even = 0; // Find number of even and odd integers for (var i = 0; i < n; i++) { if (arr[i] % 2 == 1) odd++; else even++; } // If it possible to make // lexicographically smaller if (odd > 0 && even > 0) arr.sort((a,b)=>a-b); // Print the array for (i = 0; i < n; i++) document.write(arr[i] + " ");}// Driver codevar arr = [ 1, 5, 4, 3, 2 ];var n = arr.length;// Function calllexicographically_smaller(arr, n);// This code is contributed by 29AjayKumar </script> |
1 2 3 4 5
Time Complexity: O(N log N)
Auxiliary Space: O(1), no extra space is required, so it is a constant.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
