Java >> Java tutorial >  >> Java

Java-program til at identificere det manglende nummer i et givet array

Java

I denne øvelse lærer vi, hvordan man identificerer de manglende elementer i et array. Det betyder, at vi skal finde det ene manglende element i listen over n-1 heltal, hvor heltal er i intervallet 1 til n, og der ikke er nogen dubletter på listen. Men før du går videre, hvis du ikke er bekendt med begreberne for arrayet, så tjek artiklen Arrays in Java.

Input: 1 2 4 5 6

Output :Manglende element er 3.

Program 1:Find manglende element ved hjælp af totalsumteknik

I dette program vil vi se, hvordan man identificerer det manglende element i arrayet ved hjælp af totalsum-teknikken. Logikken bag denne tilgang er, at vi først finder den samlede sum af alle elementerne i arrayet ved at bruge formlen sum=(n+1)*(n+2)/2. Her bruger vi formlen sum=(n+1)*(n+2)/2 i stedet for sum=(n)*(n+1)/2, fordi det samlede antal elementer her er n, men som ét element mangler, så det samlede antal summer til n+1.

Algorithme

  1. Start
  2. Deklarer matrixstørrelsen.
  3. Bed brugeren om at initialisere matrixstørrelsen.
  4. Deklarer arrayet.
  5. Bed brugeren om at initialisere array-elementerne.
  6. Beregn summen af ​​de første n naturlige tal ved hjælp af en formel som sumtotal=n*(n+1)/2
  7. Deklarer en variabel sum for at gemme summen af ​​matrixelementer.
  8. Brug af en for-løkke gennem hvert element i arrayet.
  9. Træk hvert element fra den samlede beregnede sum.
  10. Det resterende element i summen vil være det manglende element.
  11. Udskriv summen.
  12. Stop.

Nedenstående program viser, hvordan man identificerer det manglende element i arrayet ved hjælp af totalsum-teknikken.

/*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
   }
}


Indtast det samlede antal elementer 4
Indtast elementerne i arrayet 1 2 4 5
Manglende element er 3

Program 2:Find det manglende element ved hjælp af XOR-teknik

I dette program vil vi se, hvordan man identificerer det manglende element i et array ved hjælp af XOR-teknik.

Algorithme

  1. Start
  2. Deklarer matrixstørrelsen.
  3. Bed brugeren om at initialisere matrixstørrelsen.
  4. Deklarer arrayet.
  5. Bed brugeren om at initialisere array-elementerne.
  6. Deklarer to variable. Initialiser den første variabel til det første element i arrayet og den anden variabel til 1.
  7. Brug en for-løkke til at gentage alle elementerne.
  8. Find XOR for hvert element med den første variabel.
  9. Brug en anden for-løkke til at gentage alle elementerne.
  10. Find XOR for hvert element med den anden variabel.
  11. Det manglende element findes ved at tage XOR for de ovenfor resulterende variable.
  12. Udskriv det manglende element.
  13. Stop.

Nedenstående program viser, hvordan man identificerer det manglende element i arrayet ved hjælp af XOR-teknik.

/*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
   }
}


Indtast det samlede antal elementer 7
Indtast elementerne i arrayet 1 2 3 4 5 7 8
Manglende element er 6


Java tag