Given an input integer array arr which is sorted in ascending order and has numbers from 1 to n with one number missing, we need to find the missing number.
|
The algorithm finds a missing number in a sequence from 1 to N by calculating the expected arithmetic sum of all integers up to N and subtracting the actual sum of the elements present in the provided array.
|
| The method should accept following input parameters: arr (int array). Input arr should be sorted in ascending order and have numbers from 1 to n with one number missing.
|
| Initialize an int variable n to (arr.length+1), this is because, one number is missing in the array, so n is set to length of array + 1.
|
| Initialize an int variable named sumOfIntegersFrom1ToN and set it to (n*(n+1))/2; (this the mathematical formula for sum of numbers from 1 to n).
|
| Initialize a for loop, iterate through all elements of arr and store sum of all numbers in arr in a variable called sumOfArrayElements.
|
| Since one number is missing, set int variable missingNumber = sumOfIntegersFrom1ToN -sumOfArrayElements.
|
| Return missingNumber.
|
This execution trace will help you understand the code better.
For this execution, the input array is arr={1,3,4,5}
| Step | Line / Variable | Calculation / Operation | Value |
| 1 | n | 4 + 1 | 5 |
| 2 | sumOfIntegersFrom1ToN | (5 * (5 + 1)) / 2 | 15 |
| 3 | sumOfArrayElements | Initial assignment | 0 |
| 4 | Loop idx = 0 | 0 + arr[0] (1) | 1 |
| 5 | Loop idx = 1 | 1 + arr[1] (3) | 4 |
| 6 | Loop idx = 2 | 4 + arr[2] (4) | 8 |
| 7 | Loop idx = 3 | 8 + arr[3] (5) | 13 |
| 8 | missingNumber | 15 - 13 | 2 |
Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it.
Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.
public class ArrayFindMissingNumberFrom1ToN {
// Note: please make sure input array has all distinct integers from 1 to N, except the missing
// method below works find only if above condition is met !
public int arrayFindMissingNumberFrom1ToN(int[] arr) throws Exception{
int n=arr.length+1;
int sumOfIntegersFrom1ToN= (n*(n+1))/2;
int sumOfArrayElements=0;
for (int idx=0; idx < arr.length; idx++) {
sumOfArrayElements+=arr[idx];
}
int missingNumber=sumOfIntegersFrom1ToN-sumOfArrayElements;
return missingNumber;
}
public static void main(String[] args) {
int missingNumber;
ArrayFindMissingNumberFrom1ToN ap=new ArrayFindMissingNumberFrom1ToN();
try {
int[] intArray1 = {1,3,4,5};
printArraySummary(intArray1, "Original Array:");
missingNumber=ap.arrayFindMissingNumberFrom1ToN(intArray1);
System.out.print("Missing number in Array is : "+missingNumber+ "\n");
int[] intArray2 = {1};
printArraySummary(intArray2, "Original Array:");
missingNumber=ap.arrayFindMissingNumberFrom1ToN(intArray2);
System.out.print("Missing number in Array is : "+missingNumber+ "\n");
int[] intArray3 = {1,2,3,4,6};
printArraySummary(intArray3, "Original Array:");
missingNumber=ap.arrayFindMissingNumberFrom1ToN(intArray3);
System.out.print("Missing number in Array is : "+missingNumber+ "\n");
int[] intArray4 = {2,3};
printArraySummary(intArray4, "Original Array:");
missingNumber=ap.arrayFindMissingNumberFrom1ToN(intArray4);
System.out.print("Missing number in Array is : "+missingNumber+ "\n");
int[] intArray5 = {1,2,3,4,5,6};
printArraySummary(intArray5, "Original Array:");
missingNumber=ap.arrayFindMissingNumberFrom1ToN(intArray5);
System.out.print("Missing number in Array is : "+missingNumber+ "\n");
}catch (Exception exception) {
System.out.print("Exception: "+ exception);
}
}
public static void printArraySummary(int[] intArray, String label) throws Exception {
// Case 1: The input Array is null !!
if (intArray == null) { System.out.println("\n\n Input Array was null !! \n"); return; }
// Case 2: Print input Array by index (first to last)
System.out.println();
System.out.println("************************************************************************");
System.out.print(label+" : ");
int arrayIndex=0;
for (arrayIndex=0; arrayIndex < intArray.length; arrayIndex++) {
System.out.print(intArray[arrayIndex]);
if (arrayIndex < intArray.length-1) {System.out.print(",");}
}
System.out.println();
System.out.println("*************************************************************************");
System.out.println();
Thread.sleep(2000);
return;
}
}
, 
, 
