Étant donné un tableau arr[] composé de N entiers non négatifs, la tâche consiste à vérifier s’il est possible de rendre la somme du tableau égale au produit de l’élément du tableau en remplaçant exactement un élément du tableau par n’importe quel entier non négatif.
Exemples:
Saisir: arr[] = {1, 3, 4}
Sortir: Oui
Explication:
Le remplacement du dernier élément du tableau par 2 modifie le tableau en {1, 3, 2}. La somme de l’élément du tableau = 6 et Le produit de l’élément du tableau est 1*2*3 = 6. Par conséquent, imprimez Oui.
Saisir: arr[] = {1, 2, 3}
Sortir: Non
Approcher: Le problème donné peut être résolu en utilisant les observations mathématiques suivantes :
Considérez la somme des éléments du tableau comme S et le produit de l’élément du tableau comme P et après avoir remplacé tout élément du tableau X avec Oui la somme et le produit de l’élément du tableau doivent être identiques, l’équation devient :
=> S – X + Y = P * Y / X
=> Y = (S – X) / (P / X – 1)
A partir des observations ci-dessus, l’idée est de trouver la somme et le produit des éléments du tableau comme S et P puis itérer sur l’élément du tableau (disons X) et trouver la valeur de Oui en utilisant l’équation ci-dessus et s’il existe un élément de tableau ayant la valeur de Oui sous forme d’entier complet non négatif, puis imprimez Oui. Sinon, imprimez Non.
Vous trouverez ci-dessous la mise en œuvre de l’approche ci-dessus :
Python3
|
def canPossibleReplacement(N, arr): S = somme(arr) P = 1 pour i dans arr : P *= je pour x dans arr : y = (Sx)//(P / x-1) si (Sx + y) == (P * y)/x : retourner ‘Oui’ retourner ‘Non’ N, arr = 3, [1, 3, 4] print(canPossibleReplacement(N, arr)) |
Complexité temporelle : AU)
Espace auxiliaire : O(1)
Attention lecteur ! N’arrêtez pas d’apprendre maintenant. Obtenez tous les concepts importants de DSA avec le Cours auto-rythmé DSA à un prix adapté aux étudiants et devenez prêt pour l’industrie. Pour compléter votre préparation de l’apprentissage d’une langue à DS Algo et bien d’autres, veuillez vous référer Cours complet de préparation aux entretiens.
Au cas où vous souhaiteriez assister cours en direct avec des experts, veuillez vous référer Cours en direct DSA pour les professionnels en activité et Programmation compétitive en direct pour les étudiants.
