Étant donné un tableau arr(), la tâche consiste à vérifier si le tableau peut être trié à l’aide de l’opération donnée un sure nombre de fois. En une seule opération, vous pouvez échanger deux éléments adjacents si leur la somme est impaire.
Exemples:
Saisir: tab() = (1, 6, 31, 14)
Sortir: Oui
Explication: Échangez 31 et 14 (31 + 14 = 45 qui est impair). Le tableau sera (1, 6, 14, 31) qui est trié.Saisir: tab() = (4, 2)
Sortir: Non
Explication: Ici, aucun échange n’est attainable. Par conséquent, le tableau ne peut pas être trié à l’aide de l’opération donnée.
Approche: Pour résoudre le problème, suivez l’idée ci-dessous :
Les éléments adjacents ne peuvent être échangés que s’ils sont de parité différente. Le tableau donné ne peut pas être trié si un élément supérieur et de même parité vient plus tôt dans le tableau. Donc, si l’ordre des éléments pairs ou l’ordre des éléments impairs n’est pas non décroissant, il est alors unimaginable de trier le tableau donné. Nous pouvons créer deux tableaux séparés pour stocker les éléments pairs et impairs, puis vérifier si les deux tableaux sont dans un ordre non décroissant ou non séparément.
Voici les étapes de l’approche ci-dessus :
- Initialiser deux tableaux/vecteurs, disons, même() et impair() qui stockent respectivement les éléments pairs et impairs.
- Itérer le tableau donné et vérifier si arr(i) % 2 == 0poussez l’élément courant dans le tableau même()sinon poussez l’élément courant dans le tableau impair().
- Vérifiez si les deux tableaux sont séparément dans un ordre non décroissant, retournez vrai, sinon retournez fake.
Vous trouverez ci-dessous le code de l’approche ci-dessus :
C++
|
|
Complexité temporelle : SUR)
Espace Auxiliaire : SUR)
