Given a numeric string str, the task is to find the smallest integer that can be formed by swapping adjacent digits of distinct parity. Examples:
Input: 836360 Output: 338660 Explanation: 1st Swap: 836360 -> 386360 2nd Swap: 386360 -> 383660 3rd Swap: 383660 -> 338660 Input: 1003 Output: 13
Approach: We can observe that on repeated swaps, we can split the even and odd digits of str into two separate blocks. The order of digits in their respective blocks will be the same as their order of appearance in the string as swapping within a block (same parity) is not allowed. Thus, after separating str into two separate blocks, we need to traverse these two blocks and append the minimum of the two values currently pointed, to the answer. The final string generated after this operation followed by the removal of leading 0’s, if any, is the required answer. Example: The even and odd blocks int the order of their appearance in 836360 are {8, 6, 6, 0} and {3, 3} respectively. Hence the smallest number ans formed is as follows:
- ans = ans + min(8, 3) => ans = 3
- ans = ans + min(8, 3) => ans = 33
- Since, all the odd digits are exhausted, the remaining even digits need to be added one by one.
- Hence, the required answer is 338660
Below is the implementation of the above approach:Â
C++
// C++ Program to find the// smallest number possible// by swapping adjacent digits// of different parityÂ
#include <bits/stdc++.h>using namespace std;Â
// Function to return the// smallest number possiblestring findAns(string s){Â Â Â Â int digit;Â
    // Arrays to store odd and    // even digits in the order    // of their appearance in    // the given string    vector<int> odd;    vector<int> even;Â
    // Insert the odd and    // even digits    for (auto c : s) {        digit = c - '0';        if (digit & 1)            odd.push_back(digit);        else            even.push_back(digit);    }Â
    // pointer to odd digit    int i = 0;    // pointer to even digit    int j = 0;Â
    string ans = "";Â
    while (i < odd.size()           and j < even.size()) {Â
        if (odd[i] < even[j])            ans += (char)(odd[i++] + '0');        else            ans += (char)(even[j++] + '0');    }Â
    // In case number of even and    // odd digits are not equalÂ
    // If odd digits are remaining    while (i < odd.size())        ans += (char)(odd[i++] + '0');Â
    // If even digits are remaining    while (j < even.size())        ans += (char)(even[j++] + '0');Â
    // Removal of leading 0's    while (ans[0] == '0') {        ans.erase(ans.begin());    }Â
    return ans;}int main(){Â
    string s = "894687536";    cout << findAns(s);    return 0;} |
Java
// Java program to find the smallest // number possible by swapping adjacent // digits of different parityimport java.util.*;Â
class GFG{Â
// Function to return the// smallest number possiblestatic String findAns(String s){Â Â Â Â int digit;Â
    // Arrays to store odd and even     // digits in the order their     // appearance in the given String    Vector<Integer> odd =new Vector<Integer>();    Vector<Integer> even = new Vector<Integer>();Â
    // Insert the odd and    // even digits    for(char c : s.toCharArray())    {       digit = c - '0';       if (digit % 2 == 1)           odd.add(digit);       else           even.add(digit);    }Â
    // Pointer to odd digit    int i = 0;         // Pointer to even digit    int j = 0;Â
    String ans = "";Â
    while (i < odd.size() && j < even.size())    {        if (odd.get(i) < even.get(j))            ans += (char)(odd.get(i++) + '0');        else            ans += (char)(even.get(j++) + '0');    }Â
    // In case number of even and    // odd digits are not equal    // If odd digits are remaining    while (i < odd.size())        ans += (char)(odd.get(i++) + '0');Â
    // If even digits are remaining    while (j < even.size())        ans += (char)(even.get(j++) + '0');Â
    // Removal of leading 0's    while (ans.charAt(0) == '0')    {        ans = ans.substring(1);    }    return ans;}Â
// Driver codepublic static void main(String[] args){Â Â Â Â String s = "894687536";Â Â Â Â Â Â Â Â Â System.out.print(findAns(s));}}Â
// This code is contributed by 29AjayKumar |
Python3
# Python3 Program to find the # smallest number possible # by swapping adjacent digits # of different parity Â
# Function to return the # smallest number possible def findAns(s):Â
    # Arrays to store odd and     # even digits in the order     # of their appearance in     # the given string     odd = []    even = [] Â
    # Insert the odd and     # even digits              for c in s:        digit = int(c)        if (digit & 1):            odd.append(digit)        else:            even.append(digit)Â
    # pointer to odd digit     i = 0         # pointer to even digit     j = 0Â
    ans = ""Â
    while (i < len(odd) and j < len(even)):                 if (odd[i] < even[j]):            ans += str(odd[i])            i = i + 1        else:            ans += str(even[j])            j = j + 1Â
    # In case number of even and     # odd digits are not equal Â
    # If odd digits are remaining     while (i < len(odd)):        ans += str(odd[i])        i = i + 1Â
    # If even digits are remaining     while (j < len(even)):        ans += str(even[j])        j = j + 1Â
    # Removal of leading 0's     while (ans[0] == '0'):        ans = ans[1:]Â
    return ansÂ
# Driver Codes = "894687536"print(findAns(s))Â
# This code is contributed by yatin |
C#
// C# program to find the smallest // number possible by swapping adjacent // digits of different parityusing System;using System.Collections.Generic;Â
class GFG{Â
// Function to return the// smallest number possiblestatic String findAns(String s){Â Â Â Â int digit;Â
    // Arrays to store odd and even     // digits in the order their     // appearance in the given String    List<int> odd = new List<int>();    List<int> even = new List<int>();Â
    // Insert the odd and    // even digits    foreach(char c in s.ToCharArray())    {        digit = c - '0';        if (digit % 2 == 1)            odd.Add(digit);        else            even.Add(digit);    }Â
    // Pointer to odd digit    int i = 0;         // Pointer to even digit    int j = 0;Â
    String ans = "";Â
    while (i < odd.Count && j < even.Count)    {        if (odd[i] < even[j])            ans += (char)(odd[i++] + '0');        else            ans += (char)(even[j++] + '0');    }Â
    // In case number of even and    // odd digits are not equal    // If odd digits are remaining    while (i < odd.Count)        ans += (char)(odd[i++] + '0');Â
    // If even digits are remaining    while (j < even.Count)        ans += (char)(even[j++] + '0');Â
    // Removal of leading 0's    while (ans[0] == '0')    {        ans = ans.Substring(1);    }    return ans;}Â
// Driver codepublic static void Main(String[] args){Â Â Â Â String s = "894687536";Â Â Â Â Â Â Â Â Â Console.Write(findAns(s));}}Â
// This code is contributed by 29AjayKumar |
Javascript
<script>// javascript program to find the smallest // number possible by swapping adjacent // digits of different parityÂ
    // Function to return the    // smallest number possible     function findAns( s) {        var digit;Â
        // Arrays to store odd and even        // digits in the order their        // appearance in the given String        var odd = [];        var even = [];Â
        // Insert the odd and        // even digits        for (var i =0;i<s.length;i++) {            digit = s[i].charCodeAt(0) -'0'.charCodeAt(0);            if (digit % 2 == 1)                odd.push(digit);            else                even.push(digit);        }Â
        // Pointer to odd digit        var i = 0;Â
        // Pointer to even digit        var j = 0;Â
        var ans = "";Â
        while (i < odd.length && j < even.length) {            if (odd[i] < even[j])                ans += String.fromCharCode(odd[i++] + '0'.charCodeAt(0));            else                ans += String.fromCharCode(even[j++] + '0'.charCodeAt(0));        }Â
        // In case number of even and        // odd digits are not equal        // If odd digits are remaining        while (i < odd.length)            ans += String.fromCharCode(odd[i++] + '0'.charCodeAt(0));Â
        // If even digits are remaining        while (j < even.length)            ans += String.fromCharCode(even[j++] + '0'.charCodeAt(0));Â
        // Removal of leading 0's        while (ans.charAt(0) == '0') {            ans = ans.substring(1);        }        return ans;    }Â
    // Driver code        var s = "894687536";        document.write(findAns(s));Â
// This code is contributed by gauravrajput1 </script> |
Output:
846869753
Time Complexity: O(N), where N is the size of the given string.
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!
