Find the Maximum Number formed by Swapping Digits of Same Parity in Java
Given a number N, our task is to maximize a specific number N by following these defined constraints.
- The number's odd digit can only be swapped for any other odd digit that appears in the given number.
- The number's even digit can only be switched for any other even digit that appears in the given number.
Example 1:
Input:
int Num = 1234 Output:
The maximum number formed by swapping the parity is 3412
Explanation:
When the digits 3 and 1 are swapped, the result is 3214. When the digits 2 and 4 are swapped, the result is 3412. Though there might be alternative swapping sequences, it can be demonstrated that 3412 is the greatest number that can be achieved. Since the numbers 4 and 1 have different parities, we might not be able to swap them. Hence, the maximum number formed by swapping is 3412.
Example 2:
Input:
int Num = 6587
Output:
The maximum number formed by swapping the parity is 8765
Explanation:
When the digits 8 and 6 are swapped, the result is 8567. When the digits 5 and 7 are swapped, the result is 8765. Though there might be alternative swapping sequences, it can be demonstrated that 8765 is the greatest number that can be achieved. Hence, the maximum number formed by swapping is 8765.
Approach: Naive approach
If one of the digits in the given number N is even, identify the largest even element to the right of it and then swap between the two elements. Similarly, proceed the same way if the digit is odd.
Algorithm:
Step 1: Convert the given number, Num, into string str. (To make it easier to traverse through each digit of the number).
Step 2: Iterate the string from 0 to str.length()-1.
Step 2.1: Utilize variables that store the exact position (say index) and maximum value (say maxi) to the right of the current index.
Step 2.2: Iterate the string starting from j = i+1 to str.length()-1.
Step 2.2.1: Update the maxi and index if the jth digit is greater than the ith digit and the ith digit is of the same parity.
Step 2.2.2: Else, proceed with the iteration.
Step 2.3: Finally, we exchange str[i] for str[index].
Step 3: Return the string str's integer value.
Implementation:
FileName: NaiveMaxiNumberParity.java
import java.io.*;
import java.util.*;
public class NaiveMaxiNumberParity
{
static String swap(String s, int i, int j)
{
StringBuilder string = new StringBuilder(s);
string.setCharAt(i, s.charAt(j));
string.setCharAt(j, s.charAt(i));
return string.toString();
}
// Apply the function to maximize the number
public static int maximumNumber(int Num)
{
// The number in the string will be
// represented by a string.
String str = Integer.toString(Num);
// Traversing the given string (number)
for (int i = 0; i < str.length(); i++)
{
int max = str.charAt(i) - '0';
int index = i;
// To maximize the string,
//Check the ith digit using all
// of the remaining unoperated string.
for (int j = i + 1; j < str.length(); j++)
{
// If the ith and jth digits
// are both odd, then
if (max % 2 == 0 && (str.charAt(j) - '0') % 2 == 0)
{
// In the case that the jth digit
// is greater than the ith digit
if (str.charAt(j) - '0' > max)
{
max = str.charAt(j) - '0';
index = j;
}
}
// If the jth and ith digits are both even
else if (max % 2 == 1 && (str.charAt(j) - '0') % 2 == 1)
{
// In the case that the jth digit
// is greater than the ith digit
if (str.charAt(j) - '0' > max)
{
max = str.charAt(j) - '0';
index = j;
}
}
}
// Swap the ith digit with the
// greatest digit to the right.
str = swap(str, i, index);
}
// Convert a string to an integer
return Integer.parseInt(str);
}
public static void main(String[] args)
{
int Num = 6587;
System.out.print("The maximum number formed by swapping the parity is " + maximumNumber(Num));
}
}
Output:
The maximum number formed by swapping the parity is 8765
Complexity Analysis:
The Time Complexity for the above approach is O(N2), and the Space Complexity
is O(N), where N represents the length of the given string.
Approach: Efficient approach
The process for storing even and odd numbers is the same: arrange them in a non-increasing sequence. Now substitute even digits for all the stored even digits of the provided number in a non-increasing order and repeat the process for the odd digits.
Algorithm:
Step 1: Convert the supplied number Num into a string str.
Step 2: Iterate the given string str and do the following steps.
Step 2.1: Store every even number in a string called EDigit and every odd number in a different string called ODigit.
Step 2.2: Sort the two strings in a non-increasing order.
Step 3: Repeat steps 1 through 3 over again.
Step 3.1: To indicate the next even or odd digit to be chosen, use two iterators (let's say iterator1 and iterator2).
Step 3.2: In case the digit in str is even, increase iterator1 and substitute the digit from EDigit[iterator1].
Step 3.3: In case the digit in str is odd, increase iterator2 and substitute the digit from ODigit[iterator2].
Step 4: Finally, return the integer that was created from the string str.
Implementation:
FileName: MaxiNumberParityEfficient.java
import java.util.*;
import java.io.*;
// Helper class that implements the
// interface Comparator to compare a
// string's characters in an order
// that is non-increasing
class charSort implements Comparator<Character>
{
@Override public int compare(Character char1, Character char2)
{
// Ignoring case
return Character.compare(Character.toLowerCase(char2), Character.toLowerCase(char1));
}
};
public class MaxiNumberParityEfficient
{
static int maximumNumber(int Num)
{
// Store every even number.
ArrayList<Character> ODigit = new ArrayList<Character>();
// Store every odd number.
ArrayList<Character> EDigit = new ArrayList<Character>();
// Convert the given number to a char array.
char[] str = (String.valueOf(Num)).toCharArray();
for (int i = 0; i < str.length; i++)
{
// Check whether the digit is even or odd
if ((str[i] - '0') % 2 == 0)
{
EDigit.add(str[i]);
}
else
{
ODigit.add(str[i]);
}
}
// Arrange the even and odd-digit strings
// in a non-increasing order.
ODigit.sort(new charSort());
EDigit.sort(new charSort());
int i1 = 0, j1 = 0;
for (int i = 0; i < str.length; i++)
{
// If the current digit is even,
// then EDigit[i1] should be used in its place.
if ((str[i] - '0') % 2 == 0)
{
str[i] = EDigit.get(i1);
i1++;
}
// If the current digit is odd,
// then ODigit[j1] should be used in its place.
else
{
str[i] = ODigit.get(j1);
j1++;
}
}
return Integer.parseInt(new String(str));
}
public static void main(String[] args)
{
int Num = 6587;
System.out.println("The maximum number formed by swapping the parity is " + maximumNumber(Num));
}
}
Output:
The maximum number formed by swapping the parity is 8765
Complexity Analysis:
The Time Complexity for the above approach is O(N * log N), and the Space Complexity is O(N), where N represents the number of digits present in the given number.