Challenge: You are given an array of n-1
integers in the range from 1
to n
.
There are no duplicates in the array.
One integer is missing from the range, and your task is to find and return the missing number.
For example:
- Input:
[1, 2, 4, 5, 6]
- Output:
3
Conditions:
- The array will always contain unique numbers.
- The input array will contain integers in the range from
1
ton
, but one number from the range is missing. - Solve this without using extra space.
The Challenge
Write a Java method findMissingNumber
that accepts an array of integers and returns the missing number from the sequence.
Example:
Input:
javaCopy codeint[] nums = {1, 2, 3, 5};
Output:
javaCopy code4
Sample Solution:
javaCopy codepublic class MissingNumber {
public static void main(String[] args) {
int[] nums = {1, 2, 3, 5};
System.out.println(findMissingNumber(nums, 5)); // Expected output: 4
}
public static int findMissingNumber(int[] nums, int n) {
// Calculate the expected sum of numbers from 1 to n using the formula n * (n + 1) / 2
int expectedSum = n * (n + 1) / 2;
// Calculate the actual sum of the numbers in the array
int actualSum = 0;
for (int num : nums) {
actualSum += num;
}
// The missing number is the difference between the expected sum and actual sum
return expectedSum - actualSum;
}
}
Explanation:
- Expected Sum:
The sum of all numbers from1
ton
can be calculated using the formula:Sum=n×(n+1)2\text{Sum} = \frac{n \times (n + 1)}{2}Sum=2n×(n+1)This gives us the total sum of the numbers that should be present in the array. - Actual Sum:
We then calculate the sum of the numbers actually present in the array. - Missing Number:
The missing number is simply the difference between the expected sum and the actual sum.
Example Walkthrough:
For an array nums = {1, 2, 3, 5}
and n = 5
:
- The expected sum of numbers from 1 to 5 is: 5×(5+1)2=15\frac{5 \times (5 + 1)}{2} = 1525×(5+1)=15
- The actual sum of the numbers in the array is: 1+2+3+5=111 + 2 + 3 + 5 = 111+2+3+5=11
- The missing number is: 15−11=415 – 11 = 415−11=4
Leave a Comment