Dada una array arr[] que consta de N enteros positivos, la tarea es rotar los dígitos de los elementos de la array en sentido contrario a las agujas del reloj, de modo que los elementos de la array estén en forma alternativa par-impar o impar-par . Si existen varias soluciones, imprima cualquiera de ellas. De lo contrario, imprima -1 .
Ejemplos:
Entrada: arr[] = { 143, 251, 534, 232, 854 }
Salida: 143 512 345 232 485
Explicación:
Al girar arr[1] en 1 en sentido contrario a las agujas del reloj, se modifica arr[1] a 512.
Al girar arr[2] en 1 en sentido antihorario modifica arr[2] a 345.
Girando arr[4] 2 en sentido antihorario modifica arr[4] a 485.Entrada: arr[] = { 44, 23, 21, 33, 14 }
Salida: 44 23 12 33 14
Enfoque: el problema anterior se puede resolver modificando el primer elemento de la array a un número impar o un número par. El elemento de la array se puede modificar convirtiendo el número en una string y luego girando los caracteres de la string hacia la izquierda según sea necesario. Siga los pasos a continuación para resolver el problema:
- Reorganice el primer elemento de la array como un número par y verifique si los elementos restantes de la array se pueden reorganizar en pares e impares alternativamente o no. Si se encuentra que es cierto, entonces reorganice los elementos de la array en pares e impares alternativamente e imprima los elementos de la array .
- De lo contrario, reorganice el primer elemento de la array como un número impar y verifique si los elementos restantes de la array se pueden reorganizar en par-impar alternativamente o no. Si se determina que es cierto, entonces reorganice los elementos restantes de la array en pares e impares alternativamente e imprima los elementos de la array.
- De lo contrario, imprima -1 .
A continuación se muestra la implementación del enfoque anterior:
C++
// c++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
// Utility function to rotate the digits of
// array elements such that array elements are
// in placed even-odd or odd-even alternately
bool is_possible(vector<int>& arr, bool check)
{
// Checks if array can be converted
// into even-odd or odd-even form
bool exists = true;
// Store array elements
vector<int> cpy = arr;
bool flag;
// Traverse the array
for (int i = 0; i < arr.size(); i++) {
// Check if arr[i] is already
// at correct position
if (arr[i] % 2 == check) {
check = !(check);
continue;
}
// Checks if it is possible
// to modify the number arr[i]
// by rotating the digits of
// the number anticlockwise
flag = false;
// Stores the number arr[i] as
// string
string strEle = to_string(arr[i]);
// Traverse over the digits of
// the current element
for (int j = 0; j < strEle.size(); j++) {
// Checks if parity of check and
// current digit is same or not
if (int(strEle[j]) % 2 == check) {
// Rotates the string by j + 1 times
// in anticlockwise
arr[i] = stoi(strEle.substr(j + 1)
+ strEle.substr(0, j + 1));
// Marks the flag
// as true and break
flag = true;
break;
}
}
// If flag is false
if (flag == false) {
// Update exists
exists = false;
break;
}
// Changes the
// parity of check
check = !(check);
}
// Checks if arr[] cannot be
// modified, then returns false
if (!exists) {
arr = cpy;
return false;
}
// Otherwise, return true
else
return true;
}
// Function to rotate the digits of array
// elements such that array elements are
// in the form of even-odd or odd-even form
void convert_arr(vector<int>& arr)
{
// If array elements can be arranged
// in even-odd manner alternately
if (is_possible(arr, 0)) {
for (auto& i : arr)
cout << i << " ";
}
// If array elements can be arranged
// in odd-even manner alternately
else if (is_possible(arr, 1)) {
for (auto& i : arr)
cout << i << " ";
}
// Otherwise, prints -1
else
cout << "-1" << endl;
}
// Driver Code
int main()
{
vector<int> arr = { 143, 251, 534, 232, 854 };
convert_arr(arr);
}
// This code is contributed by grand_master.
Java
// java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG {
// Utility function to rotate the digits of
// array elements such that array elements are
// in placed even-odd or odd-even alternately
static boolean is_possible(int arr[], int check)
{
// Checks if array can be converted
// into even-odd or odd-even form
boolean exists = true;
// Store array elements
int cpy[] = arr.clone();
boolean flag;
// Traverse the array
for (int i = 0; i < arr.length; i++) {
// Check if arr[i] is already
// at correct position
if (arr[i] % 2 == check) {
// Changes the
// parity of check
check = (check == 0 ? 1 : 0);
continue;
}
// Checks if it is possible
// to modify the number arr[i]
// by rotating the digits of
// the number anticlockwise
flag = false;
// Stores the number arr[i] as
// string
String strEle = Integer.toString(arr[i]);
// Traverse over the digits of
// the current element
for (int j = 0; j < strEle.length(); j++) {
// Checks if parity of check and
// current digit is same or not
if ((strEle.charAt(j) - '0') % 2 == check) {
// Rotates the string by j + 1 times
// in anticlockwise
arr[i] = Integer.parseInt(
strEle.substring(j + 1)
+ strEle.substring(0, j + 1));
// Marks the flag
// as true and break
flag = true;
break;
}
}
// If flag is false
if (flag == false) {
// Update exists
exists = false;
break;
}
// Changes the
// parity of check
check = (check == 0 ? 1 : 0);
}
// Checks if arr[] cannot be
// modified, then returns false
if (!exists) {
arr = cpy;
return false;
}
// Otherwise, return true
else
return true;
}
// Function to rotate the digits of array
// elements such that array elements are
// in the form of even-odd or odd-even form
static void convert_arr(int arr[])
{
// If array elements can be arranged
// in even-odd manner alternately
if (is_possible(arr, 0)) {
for (int v : arr) {
System.out.print(v + " ");
}
}
// If array elements can be arranged
// in odd-even manner alternately
else if (is_possible(arr, 1)) {
for (int v : arr) {
System.out.print(v + " ");
}
}
// Otherwise, prints -1
else
System.out.println(-1);
}
// Driver code
public static void main(String[] args)
{
// Given array
int arr[] = { 143, 251, 534, 232, 854 };
// FUnction call
convert_arr(arr);
}
}
// This code is contributed by Kingash.
Python3
# Python program of the above approach # Utility function to rotate the digits of # array elements such that array elements are # in placed even-odd or odd-even alternately def is_possible(arr, check): # Checks if array can be converted # into even-odd or odd-even form exists = True # Store array elements cpy = arr # Traverse the array for i in range(len(arr)): # Check if arr[i] is already # at correct position if (arr[i] % 2 == check): check = not(check) continue # Checks if it is possible # to modify the number arr[i] # by rotating the digits of # the number anticlockwise flag = False # Stores the number arr[i] as # string strEle = str(arr[i]) # Traverse over the digits of # the current element for j in range(len(strEle)): # Checks if parity of check and # current digit is same or not if int(strEle[j]) % 2 == check: # Rotates the string by j + 1 times # in anticlockwise arr[i] = int(strEle[j + 1:] + strEle[:j + 1]) # Marks the flag # as true and break flag = True break # If flag is false if flag == False: # Update exists exists = False break # Changes the # parity of check check = not(check) # Checks if arr[] cannot be # modified, then returns false if not exists: arr = cpy return False # Otherwise, return True else: return True # Function to rotate the digits of array # elements such that array elements are # in the form of even-odd or odd-even form def convert_arr(arr): # If array elements can be arranged # in even-odd manner alternately if(is_possible(arr, 0)): print(*arr) # If array elements can be arranged # in odd-even manner alternately elif(is_possible(arr, 1)): print(*arr) # Otherwise, prints -1 else: print(-1) # Driver Code if __name__ == '__main__': arr = [143, 251, 534, 232, 854] convert_arr(arr) # This code is contributed by ipg2016107.
C#
// C# program of the above approach
using System;
using System.Collections.Generic;
class GFG{
// Utility function to rotate the digits of
// array elements such that array elements are
// in placed even-odd or odd-even alternately
static bool ispossible(List<int> arr, bool check)
{
// Checks if array can be converted
// into even-odd or odd-even form
bool exists = true;
// Store array elements
List<int> cpy = arr;
bool flag;
// Traverse the array
for (int i=0;i<arr.Count;i++) {
// Check if arr[i] is already
// at correct position
int temp = check ? 1 : 0;
if (arr[i] % 2 == temp) {
check = !(check);
continue;
}
// Checks if it is possible
// to modify the number arr[i]
// by rotating the digits of
// the number anticlockwise
flag = false;
// Stores the number arr[i] as
// string
int p = arr[i];
string strEle = p.ToString();
// Traverse over the digits of
// the current element
for (int j = 0; j < strEle.Length; j++) {
// Checks if parity of check and
// current digit is same or not
temp = check ? 1 : 0;
if ((int)(strEle[j] - '0')% 2 == temp) {
// Rotates the string by j + 1 times
// in anticlockwise
string s = strEle.Substring(j + 1) + strEle.Substring(0, j + 1);
arr[i] = Int32.Parse(s);
// Marks the flag
// as true and break
flag = true;
break;
}
}
// If flag is false
if (flag == false) {
// Update exists
exists = false;
break;
}
// Changes the
// parity of check
check = !(check);
}
// Checks if arr[] cannot be
// modified, then returns false
if (exists==false) {
arr = cpy;
return false;
}
// Otherwise, return true
else
return true;
}
// Function to rotate the digits of array
// elements such that array elements are
// in the form of even-odd or odd-even form
static void convert_arr(List<int> arr)
{
// If array elements can be arranged
// in even-odd manner alternately
if (ispossible(arr, false)) {
foreach (int i in arr)
Console.Write(i +" ");
}
// If array elements can be arranged
// in odd-even manner alternately
else if (ispossible(arr, true)) {
foreach (int i in arr)
Console.Write(i + " ");
}
// Otherwise, prints -1
else
Console.Write("-1");
}
// Driver Code
public static void Main()
{
List<int> arr = new List<int>(){143, 251, 534, 232, 854};
convert_arr(arr);
}
}
Javascript
<script>
// JavaScript program of the above approach
// Utility function to rotate the digits of
// array elements such that array elements are
// in placed even-odd or odd-even alternately
function is_possible(arr,check)
{
// Checks if array can be converted
// into even-odd or odd-even form
let exists = true;
// Store array elements
let cpy = arr;
let flag;
// Traverse the array
for (let i = 0; i < arr.length; i++) {
// Check if arr[i] is already
// at correct position
if (arr[i] % 2 == check) {
check = !(check);
continue;
}
// Checks if it is possible
// to modify the number arr[i]
// by rotating the digits of
// the number anticlockwise
flag = false;
// Stores the number arr[i] as
// string
let strEle = arr[i].toString();
// Traverse over the digits of
// the current element
for (let j = 0; j < strEle.length; j++) {
// Checks if parity of check and
// current digit is same or not
if (strEle[j].charCodeAt() % 2 == check) {
// Rotates the string by j + 1 times
// in anticlockwise
arr[i] = parseInt(strEle.substr(j + 1)
+ strEle.substr(0, j + 1));
// Marks the flag
// as true and break
flag = true;
break;
}
}
// If flag is false
if (flag == false) {
// Update exists
exists = false;
break;
}
// Changes the
// parity of check
check = !(check);
}
// Checks if arr[] cannot be
// modified, then returns false
if (!exists) {
arr = cpy;
return false;
}
// Otherwise, return true
else
return true;
}
// Function to rotate the digits of array
// elements such that array elements are
// in the form of even-odd or odd-even form
function convert_arr(arr)
{
// If array elements can be arranged
// in even-odd manner alternately
if (is_possible(arr, 0)) {
for (let i = 0; i < arr.length; i++)
document.write(arr[i] + " ");
}
// If array elements can be arranged
// in odd-even manner alternately
else if (is_possible(arr, 1)) {
for (let i = 0; i < arr.length; i++)
document.write(arr[i] + " ");
}
// Otherwise, prints -1
else
document.write("-1");
}
// Driver Code
let arr = [ 143, 251, 534, 232, 854 ];
convert_arr(arr);
</script>
Producción:
314 251 534 223 854
Complejidad de tiempo: O (N), ya que estamos usando un bucle para atravesar N veces.
Espacio auxiliar: O(N), ya que estamos usando espacio adicional para copiar.
Publicación traducida automáticamente
Artículo escrito por rohitsingh07052 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA