Dado un número N, la tarea es maximizar este número siguiendo las condiciones dadas:
- El dígito impar del número solo se puede intercambiar por cualquier dígito impar presente en el número dado.
- El dígito par del número solo se puede intercambiar por cualquier dígito par presente en el número dado.
Ejemplos:
Entrada: N = 234
Salida: 432
Explicación: El índice 0 se intercambia con el índice 2.Entrada: N = 6587
Salida : 8765
Explicación: El índice 0 se intercambia con el índice 2.
El primer índice se intercambia con el tercer índice.
Enfoque ingenuo: si un dígito en el número dado N es par , encuentre el elemento más grande a su derecha que también es par y finalmente intercambie ambos . haz lo mismo, si el dígito es impar.
Siga los pasos mencionados a continuación para implementar la idea:
- Convierta el número N dado en una string s (esto facilitará el desplazamiento de cada dígito del número)
- Iterar la string de 0 a s.length()-1 :
- Use variables para almacenar el valor máximo a la derecha del índice actual (digamos maxi ) y su posición (digamos idx ).
- Iterar la string de j = i+1 a s.length()-1
- Si tanto el i- ésimo dígito como el j-ésimo dígito tienen la misma paridad y el j-ésimo dígito es mayor que el i-ésimo , actualice maxi e idx .
- De lo contrario, continúa con la iteración.
- Finalmente intercambie s[i] con s[idx]
- Devuelve el valor entero de la string s .
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>
Producción
8765
Complejidad del tiempo:
Espacio Auxiliar:
Siga los pasos mencionados a continuación para implementar la idea.
- Convierta el número dado N en la string s .
- Iterar sobre s y hacer lo siguiente:
- Almacene todos los dígitos pares en una string (por ejemplo, evenDigit ) y todos los dígitos impares en otra string (por ejemplo, oddDigit ).
- Ordene ambas strings en orden no creciente.
- Iterar sobre s y hacer lo siguiente:
- Utilice dos iteradores (por ejemplo, itr1 e itr2 ) para señalar el siguiente dígito par o impar que se va a elegir.
- Si el dígito en s es par, reemplácelo con el dígito en evenDigit[itr1] e incremente itr1.
- Si el dígito en s es impar, reemplácelo con el dígito en oddDigit[itr2] e incremente itr2.
- Finalmente, convierta la string s en un número entero y devuélvalo.
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>
Producción
8765
Complejidad del tiempo:
Espacio Auxiliar:
Publicación traducida automáticamente
Artículo escrito por prathamjha5683 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA