Smallest Missing Integer Greater than Sequential Prefix Sum in Java
Given the integer array arr, which has a 0-index. If, for every 1 <= j <= i, arr[j] = arr[j - 1] + 1, then a prefix arr[0..i] is sequential. Specifically, the prefix that can be made up only of arr[0] is consecutive. It is our task to retrieve the lowest missing integer (x) from arr such that x equals or exceeds the sum of the longest consecutive prefix.
Example 1:
Input:
int arr = [1, 2, 3, 5, 6, 7]
Output:
The smallest missing integer is: 8
Explanation:
The [3,5] has a sum of 8 and is the longest consecutive prefix of numbers. Since the number 8 is not present in the array, it is the smallest missing integer that is greater than or equal to the total of the longest consecutive prefix.
Example 2:
Input:
int arr = [1, 2, 3, 2, 5]
Output:
The smallest missing integer is: 6
Explanation:
The [1, 2, 3] has a sum of 6 and is the longest consecutive prefix of numbers. Since the number 6 is not present in the array, it is the smallest missing integer that is greater than or equal to the total of the longest consecutive prefix.
Example 3:
Input:
int arr = [3, 4, 5, 1, 12, 14, 13]
Output:
The smallest missing integer is: 15
Explanation:
The longest sequential prefix of nums is [3,4,5] with a sum of 12. 12, 13, and 14 belong to the array, while 15 does not. Therefore, 15 is the smallest missing integer greater than or equal to the sum of the longest sequential prefix.
Approach: Using HashSet
Algorithm:
Step 1: Initialize the initial value of an integer variable called Sum to the array's first number.
Step 2: Calculate the input array's size.
Step 3: Iterate through the array's elements, starting at index 1 and ending at n - 1.
Step 4: Check that the current element is not equivalent to the element previous to it (and + 1).
Step 5: Exit the loop if the sequence is missing.
Step 6: Else, Add the currently selected element to Sum
Step 7: Converting Array to Set
Step 7.1: For converting the array of numbers into a set, call the toSet function.
Step 8: Finding the Missing Integer
Step 8.1: Verify that the set does not consist of the current partial sum Sum.
Step 8.2: Else, return Sum as the number that is missing.
Step 8.3: To determine the next possibly missing integer, increment the sum.
Step 9: Return the sum.
Implementation:
FileName: HashSetMissingInteger.java
import java.util.HashSet;
import java.util.Set;
import java.io.*;
public class HashSetMissingInteger
{
public int SmallestmissingInteger(int[] arr)
{
// Initialising the sum variable to the first value in the array arr, which is the partial sum of the series.
int Sum = arr[0];
for (int i = 1; i < arr.length; i++)
{
if (arr[i] != arr[i - 1] + 1)
{
break;
}
Sum += arr[i];
}
Set<Integer> set = toSet(arr);
while (true)
{
if (!set.contains(Sum))
{
return Sum;
}
Sum++;
}
}
private Set<Integer> toSet(int[] arr)
{
// Iterating through the array's elements, each element is added to the HashSet.
Set<Integer> set = new HashSet<>();
for (int i : arr) set.add(i);
// returns the HashSet that includes every element in the array.
return set;
}
public static void main(String[] args)
{
HashSetMissingInteger obj = new HashSetMissingInteger();
int[] arr = {1, 2, 3, 5, 6, 7};
int result = obj.SmallestmissingInteger(arr);
System.out.println("The smallest missing integer is: " + result);
}
}
Output:
The smallest missing integer is: 8
Complexity Analysis:
The time complexity for the above approach is O(n), and the space complexity is O(n), where n represents the size of the given array arr.
Approach: Using Prefix Sum and sorting
Algorithm:
Step 1: Initialization of a variable called sum to 0 to store the cumulative sum.
Step 2: To calculate the index, initialize an integer variable called index to 0.
Step 3: Determine exactly the size that the input ArrayList N is.
Step 4: Find the Missing Integer.
Step 4.1: Iterate over the ArrayList's entries from index 0 to N - 2.
Step 4.2: Determine if the next element present in the sequence is exactly 1 greater than the present element.
Step 4.2.1: Update the index and add the current element to the sum.
Step 4.2.2: Else, break the loop, change the index, and move on to step 6.
Step 5: Handle to the array's last element.
Step 5.1: Verify that the last element belongs in the sequence.
Step 5.2.1: Add it to the total Sum.
Step 5.2.2: Else, add the element at the index.
Step 6: Increment the sum until a value that is missing from the input ArrayList arr is found.
Step 7: Return the sum's value as the missing integer.
Implementation:
FileName: SortingMissingNumber.java
import java.util.*;
import java.io.*;
public class SortingMissingNumber
{
public int SmallestmissingInteger(ArrayList<Integer> arr)
{
long sum = 0;
int index = 0;
int N = arr.size();
// From the first to the second-to-last element, the ArrayList nums are iterated over in this loop.
for (int i = 0; i < N - 1; i++)
{
// Calculates whether the element after this one in the sequence is exactly one more than the one before it.
if (arr.get(i + 1) == arr.get(i) + 1)
{
sum += arr.get(i);
index = i;
}
else
{
index = i;
break;
}
}
// Verifies that the last element is included in the sequence.
// In such case, add it to the sum; if not,
//Add the element at the index.
if (index == N - 2 && arr.get(N - 2) + 1 == arr.get(N - 1))
{
sum += arr.get(N - 1);
}
else
{
sum += arr.get(index);
}
while (arr.contains((int) sum))
{
sum++;
}
// Missing integer is returned.
return (int) sum;
}
public static void main(String[] args)
{
SortingMissingNumber obj = new SortingMissingNumber();
ArrayList<Integer> arr = new ArrayList<>();
arr.add(1);
arr.add(2);
arr.add(3);
arr.add(5);
arr.add(6);
arr.add(7);
int result = obj.SmallestmissingInteger(arr);
System.out.println("The smallest missing integer is: " + result);
}
}
Output:
The smallest missing integer is: 8
Complexity Analysis:
The time complexity for the above approach is O(n), and the space complexity is O(n), where n represents the size of the given array arr.