Find the maximum number formed by swapping digits of same parity

0 0 11 minutes read

Given a number N, the task is to maximize this number by following the given conditions:

The odd digit of the number can only be swapped by any odd digit present in the given number.
The even digit of the number can only be swapped by any even digit present in the given number.

Examples:

Input: N = 234
Output: 432
Explanation: The 0th index is swapped with 2nd index.

Input: N = 6587
Output: 8765
Explanation: The 0th index is swapped with 2nd index.
The 1st index is swapped with 3rd index.

Naive approach: If a digit in the given number N is even then find the greatest element to its right which is also even and finally swap both. similarly do the same, if the digit is odd.

Follow the steps mentioned below to implement the idea:

Convert the given number N into string s (This will make traversing on each digit of the number easy)
Iterate the string from 0 to s.length()-1:
- Use variables to store the maximum value to the right of current index (say maxi) and its position (say idx).
- Iterate the string from j = i+1 to s.length()-1
  - If both ith digit and jth digit is of the same parity and jth digit is greater than ith, then update the maxi and idx.
  - Otherwise, continue the iteration.
- Finally swap s[i] with s[idx]
Return the integer value of the string s.

Below is the implementation of the above approach.

C++

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to maximize the number
int maximizedNumber(int num)
{
    // String will be used to represent the
    // number in string
    string s = to_string(num);
 
    // Traversing the string
    for (int i = 0; i < s.length(); i++) {
        int maxi = s[i] - '0';
        int idx = i;
 
        // Check ith digit with all
        // the remaining unoperated
        // string to maximize the string
        for (int j = i + 1; j < s.length();
             j++) {
 
            // If both the ith and
            // jth digit is odd
            if (maxi % 2 == 0
                && (s[j] - '0') % 2 == 0) {
 
                // If the jth digit is
                // greater than the ith digit
                if (s[j] - '0' > maxi) {
                    maxi = s[j] - '0';
                    idx = j;
                }
            }
 
            // If both ith and
            // jth digit is even
            else if (maxi % 2 == 1
                     && (s[j] - '0') % 2 == 1) {
 
                // If the jth digit is
                // greater than ith digit.
                if (s[j] - '0' > maxi) {
                    maxi = s[j] - '0';
                    idx = j;
                }
            }
        }
 
        // Swap the largest digit to the right
        // of ith digit with ith digit
        swap(s[i], s[idx]);
    }
 
    // Convert string into integer
    return stoi(s);
}
 
// Driver code
int main()
{
    int N = 6587;
 
    // Function call
    cout << maximizedNumber(N);
    return 0;
}

Java

// Java code to implement the approach
import java.io.*;
import java.util.*;
 
class GFG {
  static String swap(String str, int i, int j)
  {
    StringBuilder sb = new StringBuilder(str);
    sb.setCharAt(i, str.charAt(j));
    sb.setCharAt(j, str.charAt(i));
    return sb.toString();
  }
 
  // Function to maximize the number
  public static int maximizedNumber(int num)
  {
    // String will be used to represent the
    // number in string
    String s = Integer.toString(num);
 
    // Traversing the string
    for (int i = 0; i < s.length(); i++) {
      int maxi = s.charAt(i) - '0';
      int idx = i;
 
      // Check ith digit with all
      // the remaining unoperated
      // string to maximize the string
      for (int j = i + 1; j < s.length(); j++) {
 
        // If both the ith and
        // jth digit is odd
        if (maxi % 2 == 0
            && (s.charAt(j) - '0') % 2 == 0) {
 
          // If the jth digit is
          // greater than the ith digit
          if (s.charAt(j) - '0' > maxi) {
            maxi = s.charAt(j) - '0';
            idx = j;
          }
        }
 
        // If both ith and
        // jth digit is even
        else if (maxi % 2 == 1
                 && (s.charAt(j) - '0') % 2 == 1) {
 
          // If the jth digit is
          // greater than ith digit.
          if (s.charAt(j) - '0' > maxi) {
            maxi = s.charAt(j) - '0';
            idx = j;
          }
        }
      }
 
      // Swap the largest digit to the right
      // of ith digit with ith digit
      s = swap(s, i, idx);
    }
 
    // Convert string into integer
    return Integer.parseInt(s);
  }
 
  public static void main(String[] args)
  {
    int N = 6587;
 
    // Function call
    System.out.print(maximizedNumber(N));
  }
}
 
// This code is contributed by Rohit Pradhan

Python3

# Python code to implement the approach
 
# Function to maximize the number
def maximizedNumber(num):
 
    # Array String will be used to represent the
    # number in string
    s = list(str(num))
 
    # Traversing the string
    for i in range(len(s)):
        maxi = int(s[i])
        idx = i
 
        # Check ith digit with all
        # the remaining unoperated
        # string to maximize the string
        for j in range(i + 1,len(s)):
 
            # If both the ith and
            # jth digit is odd
            if ((maxi % 2 == 0) and (int(s[j]) % 2 == 0)):
 
                # If the jth digit is
                # greater than the ith digit
                if (int(s[j]) > maxi):
                    maxi = int(s[j])
                    idx = j
 
            # If both ith and
            # jth digit is even
            elif ((maxi % 2 == 1) and (int(s[j]) % 2 == 1)):
 
                # If the jth digit is
                # greater than ith digit.
                if (int(s[j]) > maxi):
                    maxi = int(s[j])
                    idx = j
 
        # Swap the largest digit to the right
        # of ith digit with ith digit
        s[i],s[idx] = s[idx],s[i]
 
    # Convert string into integer
    return ''.join(s)
 
# Driver code
N = 6587
 
# Function call
print(maximizedNumber(N))
 
# This code is contributed by shinjanpatra

C#

// C# code to implement the approach
using System;
 
public class GFG 
{
   
  // Function to maximize the number
  public static int maximizedNumber(int num)
  {
     
    // String will be used to represent the
    // number in string
    string s = num.ToString();
 
    // Traversing the string
    for (int i = 0; i < s.Length; i++) {
      int maxi = s[i] - '0';
      int idx = i;
 
      // Check ith digit with all
      // the remaining unoperated
      // string to maximize the string
      for (int j = i + 1; j < s.Length; j++) {
 
        // If both the ith and
        // jth digit is odd
        if (maxi % 2 == 0
            && (s[j] - '0') % 2 == 0) {
 
          // If the jth digit is
          // greater than the ith digit
          if (s[j] - '0' > maxi) {
            maxi = s[j] - '0';
            idx = j;
          }
        }
 
        // If both ith and
        // jth digit is even
        else if (maxi % 2 == 1
                 && (s[j] - '0') % 2 == 1) {
 
          // If the jth digit is
          // greater than ith digit.
          if (s[j] - '0' > maxi) {
            maxi = s[j] - '0';
            idx = j;
          }
        }
      }
 
      // Swap the largest digit to the right
      // of ith digit with ith digit
      string swap = s.Substring(i, 1);
      s = s.Remove(i, 1).Insert(i,
                                s.Substring(idx, 1));
      s = s.Remove(idx, 1).Insert(idx, swap);
    }
 
    // Convert string into integer
    return Int32.Parse(s);
  }
  public static void Main(string[] args)
  {
    int N = 6587;
 
    // Function call
    Console.WriteLine(maximizedNumber(N));
  }
}
 
// This code is contributed by phasing17

Javascript

<script>
// JavaScript code to implement the approach
 
// Function to maximize the number
function maximizedNumber(num)
{
    // Array String will be used to represent the
    // number in string
    var s = num.toString().split('');
 
    // Traversing the string
    for (var i = 0; i < s.length; i++) {
        var maxi = parseInt(s[i]);
        var idx = i;
 
        // Check ith digit with all
        // the remaining unoperated
        // string to maximize the string
        for (var j = i + 1; j < s.length;
             j++) {
 
            // If both the ith and
            // jth digit is odd
            if ((maxi % 2 == 0)
                && (parseInt(s[j]) % 2 == 0)) {
 
                // If the jth digit is
                // greater than the ith digit
                if (parseInt(s[j]) > maxi) {
                    maxi = parseInt(s[j]);
                    idx = j;
                }
            }
 
            // If both ith and
            // jth digit is even
            else if ((maxi % 2 == 1)
                     && (parseInt(s[j])) % 2 == 1) {
 
                // If the jth digit is
                // greater than ith digit.
                if (parseInt(s[j]) > maxi) {
                    maxi = parseInt(s[j]);
                    idx = j;
                }
            }
        }
 
        // Swap the largest digit to the right
        // of ith digit with ith digit
        var temp = s[i];
        s[i] = s[idx];
        s[idx] = temp;
    }
 
    // Convert string into integer
    return (s.join(''));
}
 
// Driver code
var N = 6587;
 
// Function call
document.write(maximizedNumber(N));
 
// This code is contributed by phasing17
</script>

Output

Time Complexity: O(N²), Where N is the length of the given string.
Auxiliary Space: O(N)

Efficient approach: This problem can be solved efficiently based on the following idea:

Store all even digits in non-increasing order and do the same for odd digits.
Now replace all stored even digits of given number in non-increasing order with even digits in it and do the same for odd digits.

Follow the steps mentioned below to implement the idea.

Convert given number N into string s.
Iterate over s and do the following:
- Store all even digits in a string (say evenDigit) and all odd digits in another string (say oddDigit).
- Sort both the strings in non-increasing order.
Iterate over s and do the following:
- Use two iterators (say itr1 and itr2) to point to the next even or odd digit to be picked.
- If the digit in s is even, then replace it with the digit in evenDigit[itr1] and increment itr1.
- If the digit in s is odd, then replace it with the digit in oddDigit[itr2] and increment itr2.
Finally, convert the string s into an integer and return it.

Below is the implementation of the above approach.

C++

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to maximize the number
int maximizedNumber(int num)
{
    // Store all even digits
    string oddDigit = "";
 
    // Store all odd digits
    string evenDigit = "";
 
    // Convert given number into string
    string s = to_string(num);
 
    for (int i = 0; i < s.size(); i++) {
        // Check if digit is even or odd
        if ((s[i] - '0') % 2 == 0) {
            evenDigit += s[i];
        }
        else {
            oddDigit += s[i];
        }
    }
 
    // Sort oddDigit and evenDigit string
    // in non-increasing order.
    sort(oddDigit.begin(), oddDigit.end(),
         greater<int>());
    sort(evenDigit.begin(), evenDigit.end(),
         greater<int>());
 
    int i1 = 0, j1 = 0;
 
    for (int i = 0; i < s.size(); i++) {
 
        // If the current digit is even
        // then replace it with evenDigit[i1]
        if ((s[i] - '0') % 2 == 0) {
            s[i] = evenDigit[i1];
            i1++;
        }
 
        // If the current digit is odd then
        // replace it with the oddDigit[j1]
        else {
            s[i] = oddDigit[j1];
            j1++;
        }
    }
 
    return stoi(s);
}
 
// Driver code
int main()
{
    int N = 6587;
 
    // Function call
    cout << maximizedNumber(N);
    return 0;
}

Java

// Java code to implement the approach
import java.util.*;
 
// Helper class implementing Comparator interface
// to compare characters of a string in non
// increasing order
class charSort implements Comparator<Character> {
 
  @Override public int compare(Character c1, Character c2)
  {
    // Ignoring case
    return Character.compare(Character.toLowerCase(c2),
                             Character.toLowerCase(c1));
  }
};
 
class GFG {
 
  // Function to maximize the number
  static int maximizedNumber(int num)
  {
    // Store all even digits
    ArrayList<Character> oddDigit
      = new ArrayList<Character>();
 
    // Store all odd digits
    ArrayList<Character> evenDigit
      = new ArrayList<Character>();
 
    // Convert given number into char array
    char[] s = (String.valueOf(num)).toCharArray();
 
    for (int i = 0; i < s.length; i++) {
      // Check if digit is even or odd
      if ((s[i] - '0') % 2 == 0) {
        evenDigit.add(s[i]);
      }
      else {
        oddDigit.add(s[i]);
      }
    }
 
    // Sort oddDigit and evenDigit string
    // in non-increasing order.
    oddDigit.sort(new charSort());
    evenDigit.sort(new charSort());
 
    int i1 = 0, j1 = 0;
 
    for (int i = 0; i < s.length; i++) {
 
      // If the current digit is even
      // then replace it with evenDigit[i1]
      if ((s[i] - '0') % 2 == 0) {
        s[i] = evenDigit.get(i1);
        i1++;
      }
 
      // If the current digit is odd then
      // replace it with the oddDigit[j1]
      else {
        s[i] = oddDigit.get(j1);
        j1++;
      }
    }
 
    return Integer.parseInt(new String(s));
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int N = 6587;
 
    // Function call
    System.out.println(maximizedNumber(N));
  }
}
 
// This code is contributed by phasing17

Python3

# Python3 code to implement the approach
 
# Function to maximize the number
def maximizedNumber(num):
 
    # Store all even digits
    oddDigit = "";
 
    # Store all odd digits
    evenDigit = "";
 
    # Convert given number into string
    s = list(str(num))
 
    for i in range(len(s)):
        # Check if digit is even or odd
        if (int(s[i]) % 2 == 0):
            evenDigit += s[i];
         
        else:
            oddDigit += s[i];
     
    oddDigit = list(oddDigit)
    evenDigit = list(evenDigit)
     
    # Sort oddDigit and evenDigit string
    # in non-increasing order.
    oddDigit.sort();
    oddDigit.reverse();
    evenDigit.sort();
    evenDigit.reverse();
 
    i1 = 0;
    j1 = 0;
 
    for i in range(len(s)):
 
        # If the current digit is even
        # then replace it with evenDigit[i1]
        if (int(s[i]) % 2 == 0):
            s[i] = evenDigit[i1];
            i1 += 1
         
 
        # If the current digit is odd then
        # replace it with the oddDigit[j1]
        else :
            s[i] = oddDigit[j1];
            j1 += 1
 
    return "".join(s)
 
# Driver code
N = 6587;
 
#Function call
print(maximizedNumber(N));
 
# This code is contributed by phasing17

C#

// C# code to implement the approach
using System;
using System.Collections.Generic;
 
// Helper class implementing Comparator interface
// to compare characters of a string in non
// increasing order
class charSort : Comparer<char> {
 
  public override int Compare(char c1, char c2)
  {
    // Ignoring case
    return (Char.ToLower(c2))
      .CompareTo(Char.ToLower(c1));
  }
};
 
 
class GFG {
 
  // Function to maximize the number
  static int maximizedNumber(int num)
  {
    // Store all even digits
    List<char> oddDigit = new List<char>();
 
    // Store all odd digits
    List<char> evenDigit = new List<char>();
 
    // Convert given number into char array
    char[] s = (num.ToString()).ToCharArray();
 
    for (int i = 0; i < s.Length; i++) {
      // Check if digit is even or odd
      if ((s[i] - '0') % 2 == 0) {
        evenDigit.Add(s[i]);
      }
      else {
        oddDigit.Add(s[i]);
      }
    }
 
    // Sort oddDigit and evenDigit string
    // in non-increasing order.
    oddDigit.Sort(new charSort());
    evenDigit.Sort(new charSort());
 
    int i1 = 0, j1 = 0;
 
    for (int i = 0; i < s.Length; i++) {
 
      // If the current digit is even
      // then replace it with evenDigit[i1]
      if ((s[i] - '0') % 2 == 0) {
        s[i] = evenDigit[i1];
        i1++;
      }
 
      // If the current digit is odd then
      // replace it with the oddDigit[j1]
      else {
        s[i] = oddDigit[j1];
        j1++;
      }
    }
 
    return int.Parse(s);
  }
 
  // Driver Code
  public static void Main(string[] args)
  {
    int N = 6587;
 
    // Function call
    Console.WriteLine(maximizedNumber(N));
  }
}
 
// This code is contributed by phasing17

Javascript

<script>
// JavaScript code to implement the approach
 
// Function to maximize the number
function maximizedNumber(num)
{
    // Store all even digits
    var oddDigit = "";
 
    // Store all odd digits
    var evenDigit = "";
 
    // Convert given number into string
    var s = num.toString().split("");
 
    for (var i = 0; i < s.length; i++) {
        // Check if digit is even or odd
        if (parseInt(s[i]) % 2 == 0) {
            evenDigit += s[i];
        }
        else {
            oddDigit += s[i];
        }
    }
     
    oddDigit = oddDigit.split("");
    evenDigit = evenDigit.split("");
     
    // Sort oddDigit and evenDigit string
    // in non-increasing order.
    oddDigit.sort();
    oddDigit.reverse();
    evenDigit.sort();
    evenDigit.reverse();
 
    var i1 = 0;
    var j1 = 0;
 
    for (var i = 0; i < s.length; i++) {
 
        // If the current digit is even
        // then replace it with evenDigit[i1]
        if (parseInt(s[i]) % 2 == 0) {
            s[i] = evenDigit[i1];
            i1++;
        }
 
        // If the current digit is odd then
        // replace it with the oddDigit[j1]
        else {
            s[i] = oddDigit[j1];
            j1++;
        }
    }
 
    return s.join("");
}
 
// Driver code
var N = 6587;
 
// Function call
document.write(maximizedNumber(N));
 
// This code is contributed by phasing17
</script>

Output

Time Complexity: O(M * log M), Where M is the number of digits present in N.
Auxiliary Space: O(M)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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!