So here is the detailed question:
Question (1): Suppose a number is missing in a jumbled sequence of 1 to 100. So, find the missing number. So the series may look like this:
{2,4,1,100,67.....}
Solution: Sum of natural numbers is = n*(n+1)/2. So we will find the sum of the series we have and subtract it from the sum of natural numbers from 1 .. 100 and that's how we got the missing number. To illustrate the logic we will take a list of only 10 numbers.
Now let us make the situation more complicated. Suppose we do not know how many numbers are missing in the series it can be 2, 3, 4 or just any number of digits missing. How to figure out which digits are missing.
Here is the solution, see if you can figure out apart from these:
Solution (1)
Approach:
Code listing:
SO the question in the comments can be solved either by the solution given above or there is one more solution. This solution also has the complexity O(n).
So here is the solution:
Approach:
Related posts on this blog:
Checking if i=4or5or6 without using any logical operator like && or ||
Question (1): Suppose a number is missing in a jumbled sequence of 1 to 100. So, find the missing number. So the series may look like this:
{2,4,1,100,67.....}
Solution: Sum of natural numbers is = n*(n+1)/2. So we will find the sum of the series we have and subtract it from the sum of natural numbers from 1 .. 100 and that's how we got the missing number. To illustrate the logic we will take a list of only 10 numbers.
public class FindOneMissingNumber {
public static void main(String[] args) {
// in the below jumbles series of 1-10, 7 is missing
int [] arr = {9,4,5,1,10,2,6,3,8};
// Sum of numbers till 10
int sumNaturalNumbers = 10 *(10+1)/2;
int sumOurSeries=0;
for(int i=0;i<arr.length;i++){
sumOurSeries +=arr[i];
}
System.out.println("Sum of our series: "+sumOurSeries);
System.out.println("missing number= "+(sumNaturalNumbers-sumOurSeries));
}
}
Now let us make the situation more complicated. Suppose we do not know how many numbers are missing in the series it can be 2, 3, 4 or just any number of digits missing. How to figure out which digits are missing.
Here is the solution, see if you can figure out apart from these:
Solution (1)
Approach:
- Create a new array b[] of the size of missing numbers array a[] +number of digits missing
- copy the numbers from first array into second array so that b[a[i-1]] = a[i]
- Now search the second array to see which field is contains zero
- Missing fields = array positions having zero + 1
Code listing:
/**
*
* @author Dharmvir Singh
* Solution has the complexity as O(n)
*/
public class FindOneMissingNum {
public static void main(String[] args) {
// two numbers are missing: 2, 6, 10
int a [] = {3,5,7,1,4,8,9};
int countOfMissingDigits=3;
int b [] = new int [a.length+countOfMissingDigits];
for (int i = 0; i < a.length; i++) {
b[(a[i]-1)]=a[i];
}
for (int i = 0; i < b.length; i++) {
if(b[i]==0){
System.out.println("missing number is"+(i+1));
}
}
}
}
SO the question in the comments can be solved either by the solution given above or there is one more solution. This solution also has the complexity O(n).
So here is the solution:
Approach:
- Suppose series is a[]={4,2,3,1,2}. Suppose positions here are starting from i= o to 4
- Start marking the numbers at positions a[a[i]-1] as negative.
- In above process exclude all the numbers which are already marked negative(-)
- All the positions will have their numbers marked (-) except the positions representing the missing number
public class FindMissingNum {
/**
* @param args
*/
public static void main(String[] args) {
// two numbers are missing: 2, 6
int a[] = { 3, 5, 1, 7, 1, 3, 4, 8, 7, 9 };
int t1, t;
for (int i = 0; i < a.length; i++) {
t = a[i];
// if t is already negative then make it positive as
// positions cannot be negative
if (t < 0) {
t1 = -t;
if (a[t1 - 1] > 0)
a[t1 - 1] = -a[t1 - 1];
} else {
if (a[t - 1] > 0)
a[t - 1] = -a[t - 1];
}
}
// Print the missing numbers
for (int i = 0; i < a.length; i++) {
if (a[i] > 0) {
System.out.println("Missing Number:" + (i + 1));
}
}
}
}
Related posts on this blog:
Checking if i=4or5or6 without using any logical operator like && or ||
