Home  >  Article  >  Java  >  Java program to find missing numbers

Java program to find missing numbers

WBOY
WBOYforward
2023-08-27 17:13:06613browse

Java program to find missing numbers

Missing numbers are missing numbers in a stream or array of consecutive elements. In this section, we will discuss various ways to find missing numbers in a stream of elements using java programming language.

Example of missing numbers in array

Missing numbers are numbers missing from a sequence of consecutive numbers in the array.

Consider an array;

arr=[1,2,3,4,5,6,8]

In the above array 'arr', 7 is missing, so 7 is the missing number

Example 2

Consider an array;

arr=[1,2,3,4,5,6,7,8,9,11]

In the above array 'arr', 10 is missing, so 10 is the missing number

Now, we will discuss the various ways to find missing numbers in a stream in Java.

Method 1: Use stream() and sum() methods

In this method we use stream() function and convert the array to stream and then use sum() function to calculate the sum of the stream and store it in the 'actualsum' variable and then we calculate The expected sum uses the formula n*(n 1)/2 and then we find the missing number using the expected sum - the actual sum.

algorithm

  • Initialize the array with some values.

  • Use the stream() and sum() methods to calculate the sum of an array

  • Calculate the array length and use the sum of n terms formula to find the expected sum of consecutive numbers.

  • Subtract the expected value and sum, assign it to a variable and print it.

Stream() - The 'Stream()' method is used to create a stream of elements so that we can use filter(), map(), reduce() and other methods to process data p>

Arrays.stream(collection)

sum() - This method is used to calculate the sum of all elements in the collection.

stream.sum()

Example

In this example, we will use stream() and sum() methods to find missing numbers through java.

import java.util.Arrays;
public class Main {
   public static void main(String[] args) {
      int[] array = {1, 2, 3, 5};
      int sum = Arrays.stream(array).sum(); 
      int n = array.length + 1; 
      int expectedvalue = (n * (n + 1)) / 2; 
      int lostnumber = expectedvalue - sum; 
      System.out.println("lost number " + lostnumber);
   }
}

Output

lost number 4

Method 2: Use XOR

In this method, we calculate the XOR of n values ​​and store in the expectedValue variable, then calculate the XOR of the actualValue, and finally we perform the XOR between ExpectedValue and actualValue to get the missing quantity.

algorithm

  • Initialize the array with some values.

  • Calculate the length of the array and add 1 because I think the actual number in the array should be array.length 1 and assign it to the variable "n".

  • Set the expected value to 1 and calculate the expected value using a for loop using the XOR operator until n.

  • Set the expected value to array[0] and calculate the actual value of the elements present in the array using a for loop using the XOR operator.

  • Calculate missing numbers using XOR operator of expected and actual values ​​and print

XOR operation (^) - The XOR operation performs a bitwise operation and returns 1 if both bits are 1, otherwise it returns 0. It is represented by ^.

A ^ b // where 'a' and 'b' are integers.	

Example

In this example we will use XOR operator and find missing numbers using java.

public class Main {
   public static void main(String[] args) {
      int[] array = {1, 2, 3, 5}; // input array with missing number
      int n = array.length + 1; // total number of elements if no number was missing
      int expectedValue = 1; // expected XOR value if no number was missing
      for (int i = 2; i <= n; i++) {
         expectedValue ^= i; // XOR all elements from 1 to n to get expected value
      }
      int actualValue = array[0]; // start with first element of array
      for (int i = 1; i < array.length; i++) {
         actualValue ^= array[i]; // XOR all elements of array to get actual value
      }
      int lostNumber = expectedValue ^ actualValue; // XOR expected and actual values to get lost number
      System.out.println("The lost number is " + lostNumber);
   }
}

Output

The lost number is 4

Method 3: Use HashSet

In this example, we will use the data structure Hashset and the built-in methods of Hashset to find missing numbers using java.

algorithm

  • Initialize the array with some values.

  • Create a hash set and use a for loop to iterate over the array and add the values ​​to the hash set.

  • Using a for loop, iterate i to array.length 1 and use the contains() method to check for missing values ​​in the collection and print the missing numbers.

HashSet - A hash set is an unordered collection of objects that does not allow duplicate elements.

HashSet<datatype> objName = new HashSet<datatype>();

contains() - This method checks if a value exists in the collection and returns a Boolean value.

setObjName.contains(value)

Example

In this method we store all the elements of the array in a HashSet and then iterate from 1 to array.length 1 values ​​and check if all the values ​​are present in the set, if no value is present then this Just lose the value and print it.

import java.util.Arrays;
import java.util.HashSet;

public class Main {
   public static void main(String[] args) {
      int[] array = {1, 2, 3, 5};
      HashSet<Integer> set = new HashSet<Integer>();
      for (int i : array) {
         set.add(i); 
      }
      for (int i = 1; i <= array.length + 1; i++) {
         if (!set.contains(i)) { 
            System.out.println("lost number: " + i);
            break;
         }
      }
   }
}

Output

lost number: 4

So, in this article, we learned different ways to find lost numbers using java programming language.

The above is the detailed content of Java program to find missing numbers. For more information, please follow other related articles on the PHP Chinese website!

Statement:
This article is reproduced at:tutorialspoint.com. If there is any infringement, please contact admin@php.cn delete