Java >> Tutoriel Java >  >> Java

Programme Java pour identifier le numéro manquant dans un tableau donné

Java

Dans ce tutoriel, nous allons apprendre à identifier les éléments manquants dans un tableau. Cela signifie que nous devons trouver cet élément manquant dans la liste des entiers n-1 où les entiers sont compris entre 1 et n et il n'y a pas de doublons dans la liste. Mais avant d'aller plus loin, si vous n'êtes pas familier avec les concepts du tableau, alors consultez l'article Tableaux en Java.

Saisie : 1 2 4 5 6

Sortie :L'élément manquant est 3.

Programme 1 :Trouver l'élément manquant à l'aide de la technique de la somme totale

Dans ce programme, nous verrons comment identifier l'élément manquant dans le tableau en utilisant la technique de la somme totale. La logique derrière cette approche est que nous trouvons d'abord la somme totale de tous les éléments du tableau en utilisant la formule sum=(n+1)*(n+2)/2. Ici, nous utilisons la formule sum=(n+1)*(n+2)/2 au lieu de sum=(n)*(n+1)/2 car le nombre total d'éléments ici est n mais comme un seul élément manque donc le nombre total totalise n+1.

Algorithme

  1. Démarrer
  2. Déclarez la taille du tableau.
  3. Demandez à l'utilisateur d'initialiser la taille du tableau.
  4. Déclarez le tableau.
  5. Demandez à l'utilisateur d'initialiser les éléments du tableau.
  6. Calculez la somme des n premiers nombres naturels à l'aide d'une formule telle que sumtotal=n*(n+1)/2
  7. Déclarez une somme variable pour stocker la somme des éléments du tableau.
  8. Utiliser une boucle for parcourir chaque élément du tableau.
  9. Déduisez chaque élément de la somme totale calculée.
  10. L'élément restant dans la somme sera l'élément manquant.
  11. Imprimez la somme.
  12. Arrêtez.

Le programme ci-dessous montre comment identifier l'élément manquant dans le tableau en utilisant la technique de la somme totale.

/*Java Program to find the missing element*/
import java.util.*;  
import java.util.Arrays; 

//Driver Code
public class Main  
{  
   public static void main(String args[])   
   {  
       Scanner sc=new Scanner(System.in);

      int n;    //Declare array size
      System.out.println("Enter the total number of elements ");
      n=sc.nextInt();     //Initialize array size

      int arr[]=new int[n];   //Declare array
      System.out.println("Enter the elements of the array ");
      for(int i=0; i<n ;i++)     //Initialize array
      {
          arr[i]=sc.nextInt();
      }
      
      int sum=(n+1)*(n+2)/2;   //Calculate the expected sum of all the elements from 1 to n
      for(int i=0;i<n;i++)
      {
          sum=sum-arr[i]; //Subtract each element from the sum
      }
      System.out.println("Missing Element is "+sum);  //Print the missing element
   }
}


Entrez le nombre total d'éléments 4
Entrez les éléments du tableau 1 2 4 5
L'élément manquant est 3

Programme 2 :Trouver l'élément manquant à l'aide de la technique XOR

Dans ce programme, nous verrons comment identifier l'élément manquant dans un tableau en utilisant la technique XOR.

Algorithme

  1. Démarrer
  2. Déclarez la taille du tableau.
  3. Demandez à l'utilisateur d'initialiser la taille du tableau.
  4. Déclarez le tableau.
  5. Demandez à l'utilisateur d'initialiser les éléments du tableau.
  6. Déclarez deux variables. Initialisez la première variable au premier élément du tableau et la deuxième variable à 1.
  7. Utilisez une boucle for pour parcourir tous les éléments.
  8. Trouvez le XOR de chaque élément avec la première variable.
  9. Utilisez une autre boucle for pour parcourir tous les éléments.
  10. Trouvez le XOR de chaque élément avec la deuxième variable.
  11. L'élément manquant est trouvé en prenant le XOR des variables résultantes ci-dessus.
  12. Imprimez l'élément manquant.
  13. Arrêtez.

Le programme ci-dessous montre comment identifier l'élément manquant dans le tableau à l'aide de la technique XOR.

/*Java Program to find the missing element*/
import java.util.*;  
import java.util.Arrays; 
 
//Driver Code
public class Main  
{  
   public static void main(String args[])   
   {  
       Scanner sc=new Scanner(System.in);
 
      int n;    //Declare array size
      System.out.println("Enter the total number of elements ");
      n=sc.nextInt();     //Initialize array size
 
      int arr[]=new int[n];   //Declare array
      System.out.println("Enter the elements of the array ");
      for(int i=0; i<n ;i++)     //Initialize array
      {
          arr[i]=sc.nextInt();
      }
      
        int x1 = arr[0];
        int x2 = 1;
 
        /* For xor of all the elements in array */
        for (int i = 1; i < n; i++)
            x1 = x1 ^ arr[i];
 
        /* For xor of all the elements  from 1 to n+1 */
        for (int i = 2; i <= n + 1; i++) 
        {
            x2 = x2 ^ i;
        }
        int melement=x1 ^ x2;
        System.out.println("Missing Element is "+melement);  //Print the missing element
   }
}


Entrez le nombre total d'éléments 7
Entrez les éléments du tableau 1 2 3 4 5 7 8
L'élément manquant est 6


Balise Java