Dado un entero X , la tarea es dividir su dígito en dos grupos A o B , de modo que la secuencia de dígitos no sea decreciente cuando todos los dígitos del grupo A estén ordenados seguidos por todos los dígitos del grupo B de izquierda a derecha como aparecen en X. Imprima -1 si tal partición no es posible o devuelva una string S de la misma longitud que X donde S[i] es A o B .
Ejemplos:
Entrada: X = 5164
Salida: BABA
Los dígitos en el grupo A son 1 y 4 y en el grupo B son 5 y 6. Esta partición satisface la condición cuando todos los dígitos de A se escriben y luego todos los dígitos de B se escriben como aparecen en X de izquierda a derecha, la secuencia no es decreciente, es decir, 1456.
Entrada: X = 654
Salida: -1
No es posible tal partición que resulte en una secuencia no decreciente. Por ejemplo, si consideramos BBA y escribimos la secuencia, resulta 465. De manera similar, para BAA es 546 y para AAA es 654.
Acercarse:
- Supongamos un dígito D para que todos los dígitos menores que D vayan al grupo A y todos los dígitos mayores que D vayan al grupo B.
- Para los dígitos iguales a D , irá al grupo A solo si cualquier dígito del grupo B está presente antes que él; de lo contrario, irá al grupo B.
- Después de dicha partición, verifique si forma una secuencia no decreciente. De lo contrario, intente con una D diferente .
- El valor de D varía de 0 a 9.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to generate sequence
// from the given string
vector<int> makeSeq(string s, int a[])
{
// Initialize vector to
// store sequence
vector<int> seq;
// First add all the digits
// of group A from left to right
for (int i = 0; i < s.size(); i++)
if (s[i] == 'A')
seq.push_back(a[i]);
// Then add all the digits
// of group B from left to right
for (int i = 0; i < s.size(); i++)
if (s[i] == 'B')
seq.push_back(a[i]);
// Return the sequence
return seq;
}
// Function that returns true if
// the sequence is non-decreasing
bool checkSeq(vector<int> v)
{
// Initialize result
bool check = true;
for (int i = 1; i < v.size(); i++)
if (v[i] < v[i - 1])
check = false;
return check;
}
// Function to partition the digits
// of an integer such that it satisfies
// the given conditions
string digitPartition(int X)
{
// Convert the integer to string
string num = to_string(X);
// Length of the string
int l = num.size();
// Array to store the digits
int a[l];
// Storing the digits of X in array
for (int i = 0; i < l; i++)
a[i] = (num[i] - '0');
for (int D = 0; D < 10; D++) {
// Initialize the result
string res = "";
// Loop through the digits
for (int i = 0; i < l; i++) {
// Put into group A if
// digit less than D
if (a[i] < D)
res += 'A';
// Put into group B if
// digit greater than D
else if (a[i] > D)
res += 'B';
// Put into group C if
// digit equal to D
else
res += 'C';
}
bool flag = false;
// Loop through the digits
// to decide for group C digits
for (int i = 0; i < l; i++) {
// Set flag equal to true
// if group B digit present
if (res[i] == 'B')
flag = true;
// If flag is true put in
// group A or else put in B
if (res[i] == 'C')
res[i] = flag ? 'A' : 'B';
}
// Generate the sequence from partition
vector<int> seq = makeSeq(res, a);
// Check if the sequence is
// non decreasing
if (checkSeq(seq))
return res;
}
// Return -1 if no such
// partition is possible
return "-1";
}
// Driver code
int main()
{
int X = 777147777;
cout << digitPartition(X);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Function to generate sequence
// from the given String
static Vector<Integer> makeSeq(String s, int a[])
{
// Initialize vector to
// store sequence
Vector<Integer> seq = new Vector<Integer>();
// First add all the digits
// of group A from left to right
for (int i = 0; i < s.length(); i++)
if (s.charAt(i) == 'A')
seq.add(a[i]);
// Then add all the digits
// of group B from left to right
for (int i = 0; i < s.length(); i++)
if (s.charAt(i) == 'B')
seq.add(a[i]);
// Return the sequence
return seq;
}
// Function that returns true if
// the sequence is non-decreasing
static boolean checkSeq(Vector<Integer> v)
{
// Initialize result
boolean check = true;
for (int i = 1; i < v.size(); i++)
if (v.get(i) < v.get(i - 1))
check = false;
return check;
}
// Function to partition the digits
// of an integer such that it satisfies
// the given conditions
static String digitPartition(int X)
{
// Convert the integer to String
String num = String.valueOf(X);
// Length of the String
int l = num.length();
// Array to store the digits
int []a = new int[l];
// Storing the digits of X in array
for (int i = 0; i < l; i++)
a[i] = (num.charAt(i) - '0');
for (int D = 0; D < 10; D++)
{
// Initialize the result
String res = "";
// Loop through the digits
for (int i = 0; i < l; i++)
{
// Put into group A if
// digit less than D
if (a[i] < D)
res += 'A';
// Put into group B if
// digit greater than D
else if (a[i] > D)
res += 'B';
// Put into group C if
// digit equal to D
else
res += 'C';
}
boolean flag = false;
// Loop through the digits
// to decide for group C digits
for (int i = 0; i < l; i++)
{
// Set flag equal to true
// if group B digit present
if (res.charAt(i) == 'B')
flag = true;
// If flag is true put in
// group A or else put in B
if (res.charAt(i) == 'C')
res = res.substring(0, i) +
(flag ? 'A' : 'B') + res.substring(i + 1);
}
// Generate the sequence from partition
Vector<Integer> seq = makeSeq(res, a);
// Check if the sequence is
// non decreasing
if (checkSeq(seq))
return res;
}
// Return -1 if no such
// partition is possible
return "-1";
}
// Driver code
public static void main(String[] args)
{
int X = 777147777;
System.out.print(digitPartition(X));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation of the approach
# Function to generate sequence
# from the given string
def makeSeq(s, a) :
# Initialize vector to
# store sequence
seq = [];
# First add all the digits
# of group A from left to right
for i in range(len(s)) :
if (s[i] == 'A') :
seq.append(a[i]);
# Then add all the digits
# of group B from left to right
for i in range(len(s)) :
if (s[i] == 'B') :
seq.append(a[i]);
# Return the sequence
return seq;
# Function that returns true if
# the sequence is non-decreasing
def checkSeq(v) :
# Initialize result
check = True;
for i in range(1, len(v)) :
if (v[i] < v[i - 1]) :
check = False;
return check;
# Function to partition the digits
# of an integer such that it satisfies
# the given conditions
def digitPartition(X) :
# Convert the integer to string
num = str(X);
# Length of the string
l = len(num);
# Array to store the digits
a = [0]*l;
# Storing the digits of X in array
for i in range(l) :
a[i] = (ord(num[i]) - ord('0'));
for D in range(10) :
# Initialize the result
res = "";
# Loop through the digits
for i in range(l) :
# Put into group A if
# digit less than D
if (a[i] < D) :
res += 'A';
# Put into group B if
# digit greater than D
elif (a[i] > D) :
res += 'B';
# Put into group C if
# digit equal to D
else :
res += 'C';
flag = False;
# Loop through the digits
# to decide for group C digits
for i in range(l) :
# Set flag equal to true
# if group B digit present
if (res[i] == 'B') :
flag = True;
# If flag is true put in
# group A or else put in B
res = list(res);
if (res[i] == 'C') :
res[i] = 'A' if flag else 'B';
# Generate the sequence from partition
seq = makeSeq(res, a);
# Check if the sequence is
# non decreasing
if (checkSeq(seq)) :
return "".join(res);
# Return -1 if no such
# partition is possible
return "-1";
# Driver code
if __name__ == "__main__" :
X = 777147777;
print(digitPartition(X));
# This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to generate sequence
// from the given String
static List<int> makeSeq(String s, int []a)
{
// Initialize vector to
// store sequence
List<int> seq = new List<int>();
// First add all the digits
// of group A from left to right
for (int i = 0; i < s.Length; i++)
if (s[i] == 'A')
seq.Add(a[i]);
// Then add all the digits
// of group B from left to right
for (int i = 0; i < s.Length; i++)
if (s[i] == 'B')
seq.Add(a[i]);
// Return the sequence
return seq;
}
// Function that returns true if
// the sequence is non-decreasing
static bool checkSeq(List<int> v)
{
// Initialize result
bool check = true;
for (int i = 1; i < v.Count; i++)
if (v[i] < v[i - 1])
check = false;
return check;
}
// Function to partition the digits
// of an integer such that it satisfies
// the given conditions
static String digitPartition(int X)
{
// Convert the integer to String
String num = String.Join("",X);
// Length of the String
int l = num.Length;
// Array to store the digits
int []a = new int[l];
// Storing the digits of X in array
for (int i = 0; i < l; i++)
a[i] = (num[i] - '0');
for (int D = 0; D < 10; D++)
{
// Initialize the result
String res = "";
// Loop through the digits
for (int i = 0; i < l; i++)
{
// Put into group A if
// digit less than D
if (a[i] < D)
res += 'A';
// Put into group B if
// digit greater than D
else if (a[i] > D)
res += 'B';
// Put into group C if
// digit equal to D
else
res += 'C';
}
bool flag = false;
// Loop through the digits
// to decide for group C digits
for (int i = 0; i < l; i++)
{
// Set flag equal to true
// if group B digit present
if (res[i] == 'B')
flag = true;
// If flag is true put in
// group A or else put in B
if (res[i] == 'C')
res = res.Substring(0, i) +
(flag ? 'A' : 'B') + res.Substring(i + 1);
}
// Generate the sequence from partition
List<int> seq = makeSeq(res, a);
// Check if the sequence is
// non decreasing
if (checkSeq(seq))
return res;
}
// Return -1 if no such
// partition is possible
return "-1";
}
// Driver code
public static void Main(String[] args)
{
int X = 777147777;
Console.Write(digitPartition(X));
}
}
// This code is contributed by Rajput-Ji
Producción:
BBBAABBBB
Complejidad de tiempo: O(N), donde N es la longitud de la string
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por rupesh_rao y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA