Reputation: 960
How to find missing number?
Given: two arrays as input, and find a number that is present in first array but is missing in second array.
public class Array2
{
public void missingnos(int a[],int b[])
{
for(int i=0;i<a.length;i++)
{
for(int j=i+1;j<a.length;j++)
{
if(a[i]>a[j])
{
int c=a[i];
a[i]=a[j];
a[j]=c;
}
}
System.out.print(a[i]);
}
for(int i=0;i<b.length;i++)
{
for(int j=i+1;j<b.length;j++)
{
if(b[i]>b[j])
{
int c=b[i];
b[i]=b[j];
b[j]=c;
}
}
System.out.print(b[i]);
}
int d[]=new int[a.length];
d=b;
int missing=0;
for(int i=0;i<b.length;i++)
{
if(a[i]!=d[i])
{
missing=a[i];
break;
}
}
System.out.println();
System.out.print(missing);
}
public static void main(String[] args) {
Array2 a2= new Array2();
int a[]={1,4,3,5,6};
int b[]={4,1,5,3};
a2.missingnos(a,b);
}
}
Test Case: when I remove 6 & 3 from array "a" and "b" respectively I get answer as 3 which is correct, but when i don't remove i get answer as 0.
Why is it so?
Upvotes: 0
Views: 22760
Reputation: 99
sum(first array elements) - sum(second array elements) Time complexity : o(n)+o(n-1)
Upvotes: 0
Reputation: 7
Try this:
static void Main(string[] args)
{
int[] a = {1, 4, 3, 5, 6};
int[] b = {4, 1, 5, 3};
for (int i = 0; i < a.Length; i++)
{
if(!b.Contains(a[i]))
{
Console.WriteLine("missing number: " +a[i]);
}
}
Console.ReadKey();
}
Upvotes: -1
Reputation: 367
Diff([1,2,3,4] [1,2,3]) = [4]
Diff([1,2,2,2], [1,2]) = [2,2]
Diff([2, 2, 1, 2], [1,2]) = [2,2]
Diff([1,1,1,1,1,1,2,2,2,2,2,2], [1,1,2,2]) = [1,1,1,1,2,2,2,2]
public static void main(String[] args) {
int[] a = {1,2,3,4};
int[] b = {1,2,3};
Arrays.sort(a);// The sorting only required for input example 3.
Arrays.sort(b);//
List<Integer> listA = new ArrayList<>();
for( int i = 0; i < a.length; i++ ) {
if( i >= b.length ) {
listA.add(a[i]);
}
for( int j = i; j < b.length; j++ ) {
if( a[i] == b[j] || listA.contains(a[i])) {
break;
} else {
listA.add(a[i]);
}
}
}//end of for loop
System.out.println(listA);
}
With is algorithem, only example 4 won't work.
Upvotes: 0
Reputation: 71
public class FindMissingNumbers {
public static void main(String[] args) {
// TODO Auto-generated method stub
int i,j,size1,size2;
boolean flag=false;
Scanner sc = new Scanner(System.in);
System.out.println("Enter 1st array lenght");
size1=sc.nextInt();//input array size
int[] a=new int[size1];
System.out.println("Enter "+size1+" Values of 1st array");
for(i=0;i<size1;i++){
a[i]=sc.nextInt();//read first array list
}
System.out.println("Enter 2st array lenght");
size2=sc.nextInt();//input array size
int b[]=new int[size2];
System.out.println("Enter Values of 2st array");
for(i=0;i<size2;i++){
b[i]=sc.nextInt();//read second array list
}
System.out.println("Numbers which are not present in 1nd array");
for(i=0;i<size2;i++)
{
flag=false;
for(j=0;j<size1;j++)
{
if(a[j]==b[i])
{
break;
}
else if(a[j]!=b[j] && j==size1-1){
flag=true;
}
}
if(flag==true){
System.out.println(b[i]);
flag=false;
}
}
}
}
Upvotes: 0
Reputation: 141
Here's a way to solve this problem in O(1) auxiliary space and O(n) time. The solution is subject to the below constraints:
1) arr2 has only one element missing from arr1.
2) arr2.length=arr1.length-1 OR arr2 has the missing element replaced by 0.
Solution: Simply take xor of all the elements of the two arrays. The resulting integer is the answer
Code:
public static void findMissing(){
// TODO Auto-generated method stub
int[] arr1={3,7,2,90,34};
int[] arr2={2,7,34,3};
int xor=0;
for(int i=0;i<arr1.length;i++){
xor^=arr1[i];
}
for(int i=0;i<arr2.length;i++){
xor^=arr2[i];
}
System.out.println("missing number: "+xor);
}
Why it works? Say arr1={1,2,3,4} and arr2={1,2,4}. Taking xor of all element =>
1^2^3^4^1^2^4
= (1^1)^(2^2)^(4^4)^3
= 0^0^0^3
=3
Another solution as proposed by RP- is also very good and solves this problem in the same space and time complexities, but there is a chance of an overflow while calculating sums.
Upvotes: 6
Reputation: 5837
I know this is an old question, but might help somebody. We don't really need to compare each and every element form first and second array..
Just take the sums (in long to avoid the overflow) from each array and subtract one array's sum with other array's sum. And the result is the missing number.
Upvotes: 1
Reputation: 1121
Think about this as a problem of efficient algorithm. Using nested loops on arrays will give you a O(n^2) time complexity which is not desired.
However if you use something like a HashSet your time complexity will be O(m+n) where m being the length of first array and n being the length of second array.
Something like below
import java.util.ArrayList;
import java.util.HashSet;
public class MissingNumbers {
public static Integer[] missingNumbers(Integer[] firstArray,Integer[] secondArray) {
ArrayList<Integer> alDups = new ArrayList<Integer>();
int dupCount = 0;
HashSet<Integer> setOfSecondArr = new HashSet<Integer>();
// Add second array into hash set of integers
for (int i : secondArray) {
setOfSecondArr.add(i);
}
// Now add the first array, if it gets successfully added to the set
// it means second array did not have the number
for (int i : firstArray) {
if (setOfSecondArr.add(i)) {
alDups.add(i);
dupCount++;
}
}
return alDups.toArray(new Integer[dupCount]);
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
for (int i : missingNumbers(new Integer[] { 1, 2, 3, 5, 6 },
new Integer[] { 1, 2, 4 })) {
System.out.println(i);
}
}
}
Upvotes: 1
Reputation: 531
you have complicated your logic. why use a 2nd combination of for loops when you could have done the comparison in the first for loop itself. you just need to display the numbers from the 1st array that are not present in 2nd array right
Upvotes: 0
Reputation: 692281
Your main problem is that you're trying to do it in a too complex way, and to do everything inside a single method. Sorting the arrays is not necessary, and doing it as you're doing is very inefficient, and doesn't use the Arrays.sort()
method that would do it for you.
Try to split the problem into simple tasks:
boolean isPresent(int number, int[] array)
)..
public class Arrays2 {
public static void main(String[] args) {
int[] a = {1, 4, 3, 5, 6};
int[] b = {4, 1, 5, 3};
findMissingNumber(a, b);
}
private static void findMissingNumber(int[] a, int[] b) {
for (int n : a) {
if (!isPresent(n, b)) {
System.out.println("missing number: " + n);
break;
}
}
}
private static boolean isPresent(int n, int[] b) {
for (int i : b) {
if (n == i) {
return true;
}
}
return false;
}
}
Upvotes: 1
Reputation: 51
When you have different sized arrays, then you need to stop as soon as one array reaches to its max position. Here you are getting answer as 0 because the b array has only 4 elements.
The correct code is:
int d[]=new int[a.length];
d=b;
int missing=0;
for(int i=0;i<a.length;i++)
{
if(i>=b.length || a[i]!=d[i])
{
missing=a[i];
break;
}
}
System.out.println();
System.out.print(missing);
Upvotes: 1
Reputation: 2723
for(int i=0;i<b.length;i++)
{
if(a[i]!=d[i])
{
missing=a[i];
break;
}
}
should be changed to
for(int i=0;i<min(a.Length,b.length);i++)
because you are not handling case when size of both arrays are not same .
Also
int d[]=new int[a.length]; d=b;
what if length(b)>length(a)
?
You have many errors , first try to work it on pen and paper , then transform into code .
Upvotes: 0