Welcome Guest, Not a member yet? Register   Sign In
Using stacked for loops in Java to find the missing number in an array
#1

In O(n2) time, I need to identify the missing number in an array. I can rearrange the array so that everything is in order, but I can't identify the missing number without executing another for loop, which I can't do. This is my code: The missing number in this case is 3.
Code:
public static void main(String[] args){
    int ar []={0,1,6,2,5,7,4};
    int n = ar.length;
    int temp = 0;
    int m = 0;
    for(int i = 0; i<n;i++){
        for(int j = 1; j<n;j++){
            if(ar[j-1] > ar[j]){
                temp = ar[j-1];
                ar[j-1]=ar[j];
                ar[j]=temp;

                if(ar[j-1]!=j-1) m=j;
            }
            else ar[j]=ar[j];
            if(ar[j-1]!=j-1) m=j;
        }
    }
    System.out.println(m);
}

I read an article online that said I could only do two loops and had to do two loops for O(n2). They also stated that for each value, loop through all values (inner loop) and find the smallest value greater than the current value. Skip if no higher value is found.
Reply




Theme © iAndrew 2016 - Forum software by © MyBB