CareerCup

First Let's see what all approaches we can take and then we check if it fits our requirement.
1. Brute Force: Select an element from 1 to N and check it frequency of occurrence. But this will be O(n2) and not O(n) .
2. XOR : but this technique won't work as question mentions an element can be repeated multiple times. so if element repeats 2 times or 4 times each time result of xor will be 0 so we cannot get the frequency of occurrences.
3. HashMap : We can create a HashMap in O(n) key will be elements and value will be their frequency of occurrence. But since we have to do it in O(1) space we cannot take this approach.

So we cannot opt for any of the above 3 approach. We have to check for some 4th approach.

Since we have range of numbers given to us we have to think in those lines.
Array Index is from 0 to N-1 and range is from 1 to N.
Can't we use the array as hash itself?
where array "Index-1" represents the key (element) and value stored at index will represent the "frequency of occurrence".

But how will we take care that an element present at any index is not overwritten as this can cause problem?
We can sort the array in that case value present at index i is I+1 itself.

What is the complexity of sorting the array?
O(nlogn) if we opt for heap/merge/quick sort.

But since the range of element is given to us we can sort it in O(n).

Solution goes like this....

{8,1,9,2,5,1,1,1,1} can be treated as the test data.....

{58,11,9,2,15,1,1,11,11} would be the processed data....

The process goes as follows....
8 - > add 10 to location 8 {8,1,9,2,5,1,1,11,1}
1 -> add 10 to location 1 {18,1,9,2,5,1,1,11,1}
9 -> add 10 to location 9 {18,1,9,2,5,1,1,11,11}
2 -> add 10 to location 2 {18,11,9,2,5,1,1,11,11}
5 -> add 10 to location 5 {18,11,9,2,15,1,1,11,11}
1 -> add 10 to location 1 {28,11,9,2,15,1,1,11,11}
1 -> add 10 to location 1 {38,11,9,2,15,1,1,11,11}
11 -> special process ( if element is > 10) compute the modulo and add 10 to that location...11 % 10 = 1 ...so add 10 to location 1 {48,11,9,2,15,1,1,11,11}
11 -> special process ( if element is > 10) compute the modulo and add 10 to that location...11 % 10 = 1 ...so add 10 to location 1 {58,11,9,2,15,1,1,11,11}


{58,11,9,2,15,1,1,11,11}
58 - yields 58 / 10 times 1 and the original value is 58 % 10
and so on for each value....Array values are not lost....

Note : 10 is size of the array + 1...in code we have used 20 as our array size

//Code by FINDMIND TEAM
//Done by Prabhakaran Dhandapani, NN Priya, Vaishnavi
//Guided by Sridhar Arumugasamy

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define SIZE 20

void computeAndPrint( int arr[],int size ) {
   int index = 0;
   for( index = 0 ; index < size ; index++ )
      if( arr[ index ] < ( size + 1 ) )
	 arr[ arr[ index ] - 1 ] += ( size + 1 );
      else
	 arr[ arr[ index ] % ( size + 1 ) - 1 ] += ( size + 1 );
   for( index = 0 ; index < size ; index++ )
      printf("\t\t%2d--->%2d--->%2d\n", arr[ index ] % ( size + 1 ), index + 1, arr[ index ] / ( size + 1 ));
}

void assign(int arr[], int size) {
   int index;
   randomize();
   for( index = 0 ; index < size ; index++ )
      arr[ index ] = (rand() % size) + 1;
}

void main() {
   int arr[SIZE];
   assign(arr,sizeof(arr)/2);
   computeAndPrint(arr,sizeof(arr)/2);
}

19---> 1---> 1
		 1---> 2---> 1
		20---> 3---> 1
		18---> 4---> 1
		17---> 5---> 0
		19---> 6---> 0
		 3---> 7---> 0
		 2---> 8---> 1
		 4---> 9---> 0
		 8--->10---> 0
		14--->11---> 0
		17--->12---> 0
		20--->13---> 0
		18--->14---> 3
		14--->15---> 0
		14--->16---> 1
		19--->17---> 2
		18--->18---> 4
		18--->19---> 3
		16--->20---> 2

just store value as (val + count * N)

void arrayCount(int* a, int N)
{
    for(int i=0; i<N; ++i)
    {
        int count = a[i] / N;
        int val = a[i] - count * N;
        
        a[val] += N;    
    }
    
     for(int i=0; i<N; ++i)
     {
        int count = a[i] / N;

        cout << count << " ";   
     }   
    
     cout << endl;
}

Alternative approach, encode fields which specify a normal value as positive, those that contain a count as negative, then proceed through the array. If the value we see is smaller than the index, simply decrement the field for the value (since we must already have removed any value there) if it is larger, then swap the value in that field currently with the current value and set the field value to -1, except if the field is already negative, in which case just decrement.
Afterwards, the array is filled with negative values which are the counts, so just pop a minus in front of them and voila.

It's a little hard to follow, so here's the code:

public static void countey(int [] nrs)
	{
		System.out.print("Pre: ");
		for(int j = 0; j < nrs.length; j++)
		{
			System.out.print(nrs[j] + ", ");
		}
		System.out.println();

		int i = 0;
//		for(int i = 0; i < nrs.length; i++)
		while(i < nrs.length)
		{
			System.out.print("At " + i + ": ");
			int curNr = nrs[i];
			if(curNr < 0)
			{
				i++;
//				continue;
			}
			else if(curNr <= i)
			{
				nrs[curNr]--;
				nrs[i] = 0;
				i++;
			}
			else if(nrs[curNr] < 0)
			{
				nrs[curNr]--;
				nrs[i] = 0;
				i++;
			}
			else
			{
				int temp = nrs[nrs[i]];
				nrs[nrs[i]] = -1;
				nrs[i] = temp;
			}
			
			for(int j = 0; j < nrs.length; j++)
			{
				System.out.print(nrs[j] + ", ");
			}
			System.out.println();

		}

		for(i = 0; i < nrs.length; i++)
		{
			System.out.print(-nrs[i] + ", ");
		}
		System.out.println();
		
	}

If you can generate a sequence of primes P(1) to P(n) you can create single number that will represent a digest of the data set (there are formulas out there like f(n)=n^2−n+41 that will do that for you). For example, you could use the prime sequence 3,5,7,11,13,17 to represent the set of numbers 1,2,3,4,5,6 where P(1)=3, P(2)=5, P(3)=7, P(4)=11, P(5)=13, P(6)=17.

Start with your digest as equaling 1 (call it D). Every time you see a 1, multiply it be P(1). Every time you see a 2, multiply it by P(2) etc...
Thus if your sequence is: 1,2,4,5,1,1 the 'digest' is:
D = P(1)*(2)*P(4)*P(5)*P(1)*P(1)
or another wards
D = 3 * 5 * 11 * 13 * 3 * 3

Then once you're done. Go through D and divide it with each P(n) in sequence and so long as you get a remainder 0 result you know there's another P(n) in there. In this example:

-Start dividing by 3, you will see that D divides by 3 exactly three times (hence the number 1 repeats exactly 3 times, print this information)
-Then move onto the next prime 5 and you will see that D divides by 5 exactly once (so there is exactly one instance of 2 in the list, print this information)
-Them move onto the next prime 7 and you will see that D divides by 7 zero times (so there are no 3's present in the list, print this information)

Continue doing this until the prime representing P(n) is reached. This entire process will require two passes through the data set, the initial construction of the digest D and the one more to print out the results. This solution will work so long as a number large enough to contain P(1)*(#occurrences of 1) ... * P(n) * P(1)*(#occurrences of n) can be allocated.

Simple solution in java:

public class Counter {
	public static void countOccurances(int[] input){
		System.out.println(input);
		int max = input.length;
		int[] posArr = new int[max+1];
		for(int i=0; i<max; i++){
			int num = input[i];
			posArr[num] = posArr[num]+1;
		}
		
		for(int i=1; i<=max; i++){
			if(posArr[i] < 1){
				System.out.println(i+" is missing");
			} else {
				System.out.println(i+" is appearing "+posArr[i]+" times");
			}
		}
	}
	public static void main(String[] args) {
		int[] input1 = {1,5,3,7,4,5,6,8};
		countOccurances(input1);
		
		int[] input2 = {1,5,3,7,4,5,6,8,9,5,4,10,4};
		countOccurances(input2);
	}

}

public static void elements(int[] A) {
        for (int i = 0; i < A.length; i++) {
            while (A[i] != i + 1) {
                int temp = A[A[i] - 1];
                if (temp == A[i]) {
                    break;
                }
                A[A[i] - 1] = A[i];
                A[i] = temp;
            }
        }
        System.out.println("Elements that don't exist in array A");
        for (int i = 0; i < A.length; i++) {
            if (A[i] != i + 1) {
                System.out.println(i + 1);
            } else {
                A[i] = -1;
            }
        }


        for (int i = 0; i < A.length; i++) {
            if (A[i] > 0) {
                A[A[i] - 1]--;
            }
        }
        System.out.println("Elements that exist in array A and their frequency");

        for (int i = 0; i < A.length; i++) {
            if (A[i] < 0) {
                System.out.println((i + 1) + ": " + (-A[i]));
            }

        }


    }

public static void main(String[] args) {
        // TODO code application logic here
        int[] A = {9,9,9,9,9,9,9,8,7,9,10};
        elements(A);
    }

Result:

Elements that don't exist in array A
1
2
3
4
5
6
11
Elements that exist in array A and their frequency
7: 1
8: 1
9: 8
10: 1

I suspect this is impossible under strict definitions of O(1) space. There exist no sorting algorithms with worst-case parameters of O(n) time and O(1) space. Any solution to this problem would allow you to do a linear time, constant space counting sort where the range_of_numbers <= length of array. If you could do that, you should publish a paper.

As noted in comments I've made on other answers (e.g. storing negative numbers or a number larger than len(N) in an element), all solutions thus far provided stretch the definition of O(1) space and in the general sense are O(N).

How about that idea. If you encounter element on position i and it is not equal to i. Than you have to place value a[i] to position with index a[i] e.g a[a[i]] = a[i]. But if this position is already captured with right element you go forward. It is preproccessing made by O(n). The next cycle you just scan array, and if value of element with index i isn't equal to i it means that we haven't element with value i. Here is code of my solution.

public static void checkMissedElements(int[] array){

        for (int i = 0;i < array.length;i++){
            while(array[i] != i && array[array[i]] != array[i]){
                int buf = array[i];
                array[i] = array[array[i]];
                array[buf] = buf;
            }
        }

        for (int i = 0;i < array.length;i++){
            if (array[i] != i){
                System.out.println("Element " + i + " is missed");
            }
        }
    }

This is solution on sorted array. Very basic but it is working fine.

#include<stdio.h>
#include<conio.h>
main()
{
	int arr[]={1,1,1,3,4,5,7,8,11,12,17,23,24,24,24,24,24};
	int missing_num;
	int num=0;
	int count;
	int flag=0;
	int size=sizeof(arr)/sizeof(arr[0]);
	for(int i=size-1;i>0;i--)
	{
		int k=size-1;
		int num=arr[k];
		//printf("arr[i]=[%d]   num=[%d]\n",arr[k-1],num);
		count=1;
		if(arr[k-1]==num)
		{
			 printf("The number [%d] is repeated.\n", arr[k-1]);
		}
		
		else if(arr[k-1]==num-1)
		{
		}
		else if(arr[k-1]<num-1)
		{
			missing_num=(num-1)-arr[k-1];
			//printf("missing numbers [%d]\n",missing_num);
			for(int j=num-1;j>(num-1)-(missing_num);j--)
			{
				printf("The missing number is [%d]\n",j);
			}
		}
		size=size-1;

	}
	
}

This is solution on sorted array. Very basic but it is working fine.

#include<stdio.h>
#include<conio.h>
main()
{
	int arr[]={1,1,1,3,4,5,7,8,11,12,17,23,24,24,24,24,24};
	int missing_num;
	int num=0;
	int count;
	int flag=0;
	int size=sizeof(arr)/sizeof(arr[0]);
	for(int i=size-1;i>0;i--)
	{
		int k=size-1;
		int num=arr[k];
		//printf("arr[i]=[%d]   num=[%d]\n",arr[k-1],num);
		count=1;
		if(arr[k-1]==num)
		{
			 printf("The number [%d] is repeated.\n", arr[k-1]);
		}
		
		else if(arr[k-1]==num-1)
		{
		}
		else if(arr[k-1]<num-1)
		{
			missing_num=(num-1)-arr[k-1];
			//printf("missing numbers [%d]\n",missing_num);
			for(int j=num-1;j>(num-1)-(missing_num);j--)
			{
				printf("The missing number is [%d]\n",j);
			}
		}
		size=size-1;

	}
	
}

My solution in c++ : we use the input array as a container for the counter. Elements i encoutered in the array is associated with a counter at position i-1.

#include <iostream>
#include <vector>

using namespace std;

void printMissing(vector<int> L) {
    int j, tmp;
    for (int i = 0; i < L.size(); ++i) {
        j = L[i];
        while (j > 0) {
            tmp = L[j - 1];
            L[j - 1] = (tmp > 0) ? 0 : (tmp - 1);
            j = (tmp != j) ? tmp : -1;
        }
    }
    for (int i = 0; i < L.size(); ++i) {
        cout << (i + 1) << ": ";
        cout << ((L[i] > 0) ? 0 : (- L[i] + 1)) << endl;
    }
}

int main(int argc, char **argv) {
    int ar[] = {1, 5, 3, 3, 2};
    vector<int> L(ar, ar + sizeof(ar) / sizeof(int));
    printMissing(L);
    return 0;
}

/*
Outputs :
1: 1
2: 1
3: 2
4: 0
5: 2
*/

First, we need the array to store the count since space is limited at O(1). So we need A[i] to store the count for number i. But how can we distinguish the number itself and the count? We can use negative numbers to store the count. The O(1) space is a pointer to the array for the current number. The solution is raw, with O(1) space and O(n) time, without any sorting.

E.g.

[4, 3, 2, 3, 5] => [3,3,2,-1,5] => [2,3,-1,-1,5] => [3, -1, -1, -1,5] => [0, -1, -2 ,-1, 5] => [0,-1, -2, -1, -1]

my solution:
{{
void prep(int arr, int n)
{
for(int i=0; i<n; ++i) {
int v = arr[i];
if (!v || v > n) continue;
arr[i] = 0;
while(v && v<=n) {
if (arr[v-1] > n || arr[v-1] == 0) {
arr[v-1] += v;
break;
} else {
int v1 = arr[v-1];
arr[v-1] = n+v;
v = v1;
}
}
}
}

void print_dup(int arr[], int n)
{
for(int i=0; i<n; ++i) {
if(arr[i]==0 || (arr[i]-n)/(i+1) == 1) continue;
printf("pos[%d] dup times: %d\n", i+1, (arr[i]-n)/(i+1));
}
}
void print_missing(int arr[], int n)
{
for (int i=0; i<n; ++i) {
if (!arr[i])
printf("%d missing\n", i+1);
}
}

}}

int prep(int arr[], int n)
{
    for (int i=0; i<n; ++i) {
        int v = arr[i];
        if (!v || v > n) continue;
        arr[i] = 0;
        while(v && v < n+1) {
            if (arr[v-1] > n || arr[v-1] == 0) {
                arr[v-1] += v;
                break;
            } else {
                int v1 = arr[v-1];
                arr[v-1] = n+v;
                v = v1;
            }
        }
    }
}
void print_dup(int arr[], int n)
{
    for(int i=0; i<n; ++i) {
        if(arr[i]==0 || (arr[i]-n)/(i+1) == 1) continue;
        printf("pos[%d] dup times: %d\n", i+1, (arr[i]-n)/(i+1));

    }

}

print missing is simple, check arr[i] == 0.

{{
public static void findMissingNumbers(int array[])
{
for(int i=0;i<array.length;++i)
{
if(array[i]!=(i+1) && array[array[i]-1]!=array[i])
{
int temp = array[array[i]-1];

array[array[i]-1]=array[i];

array[i]=temp;
--i;
}
}
for(int i=0;i<array.length;++i)
{
if(array[i]!= i+1 )
{
System.out.println("the number is not present " + (i+1) );

if(i==0)
array[i] = ( i + 2);
else
{
array[array[i]-1] = array[array[i]-1] + array[i];
}
}
}

for(int i=0;i<array.length;++i)
{

if(array[i]/(i+1)>=2)
{
System.out.println("The number" + (i+1) + " repeated for " + array[i]/(i+1) );
}
}
}
}}

public static void main(String[] args) {
		int arr[] = { 6, 4, 1, 4, 3, 2, 5, 2, 1 };
		freq(9, arr);
	}

	public static void freq(int n, int[] array) {

		int[] count = new int[n+1];
		for (int i = 0; i < array.length; i++) {
			count[array[i]]++;

		}
		int j=1;;
		for (int i = 1; i < count.length; i++) {

			System.out.println("number" + i + "frequency" + count[i]);
			j++;
		}

}

package code_exercise;

public class CodeExercise5 {
public static void main(String[] args) {
// swap(a1, b1);
int a[] = {10, 2, 2, 5, 3,
4, 9, 10, 9, 10, 5};
solve(a);
}

public static void swap(Integer a, Integer b) {
a ^= b;
b ^= a;
a ^= b;
}

private static void solve(int [] a) {
int tval = 0;
// determine max val
for (int i = 0; i < a.length; ) {
if (a[i] > 0) {
tval = a[a[i] - 1];
if (tval > 0) {
if (a[i] - 1 == i) {
a[a[i] - 1] = -1;
} else {
a[a[i] - 1] = -1;
a[i] = tval;
}
} else if (tval <= 0) {
a[a[i] - 1] += -1;
a[i] = 0;
i++;
}
} else {
i++;
}
}
for (int i = 0; i < a.length; i++) {
System.out.println("NUM:" + (i+1) + ", OCC:" + Math.abs(a[i]));
}
}
}

Can't we just put number back to its position, if its not right number on that position. And finally return positions with wrong number?
Each position can accommodate right number only once, so the algorithm should be O(n), and constant space complexity.

My solution is coded below, it runs in O(n) time and O(1) space

int[] count_elems(int[] ar){
		int i=0;
		while(i<ar.length){
			int j = ar[i];
			if(ar[i]>0 && ar[j]>0){
				ar[i] = ar[j];
				ar[j] = 0;
			}else{
				if(ar[i]>0){
					ar[j]--;
				}
				i++;
			}
		}
		return ar;
	}

The O(1) space requirement implies that we must re-use the given array for storing counts.
Since the range of element values is limited to the length of the array, we can simply store the count of each element at the array index of (element value -1). As we progress through the array, we can distinguish between element counts and element values by keeping the counts negative and the values as they are (between 1 and n).

function account(arr) {
    for (var i=0; i< arr.length; i++) {
        if (arr[i] <= 0) continue;
        else while (arr[i] > 0) {
            if (arr[i] -1 == i)
                arr[i] = -1;
            else if (arr[arr[i] -1] <= 0) {
                arr[arr[i] -1] -= 1;
                arr[i] = 0
            }
            else {
                temp = arr[arr[i] -1];
                arr[arr[i] -1] = -1;
                arr[i] = temp;
            }
        }
    }
    
    // TODO: print counts
}

using System;
 
public class Test
{
	public static void Main()
	{
		int[] arr = { 5, 1, 3, 5, 1 };
 
		CountNumbers(arr);
 
		for(int i = 0; i < arr.Length; i++)
		{
			var count = -1 * arr[i];
			Console.WriteLine("Element {0} appears {1} times", i+1, count);
		}
	}
 
	private static void CountNumbers(int[] arr)
	{
		for(int i = 0; i < arr.Length; i++)
		{
			var elem = arr[i];
 
			if (elem > 0)
			{
				var value = elem;
				arr[i] = 0;
				InsertElem(arr, value);
			}
		}
	}
 
	private static void InsertElem(int[] arr, int elem)
	{
		var aux = arr[elem-1];
 
		if (aux > 0)
		{
			arr[elem-1] = -1;
			InsertElem(arr, aux);
		}
		else
		{
			arr[elem-1] += -1;
		}
	}
}

The worst case would be when you have to call InsertElem for every number, this will take an extra n steps.
So it will take n to print + n to run through all elements + n in the worst case when we have to recurs through all elements, so it is O(3*n) which is O(n). Since it's inline, it's O(1) space.

def print_frequency(array):
    n = len(array)
    for i in range(1, n+1):
        k = array[i-1] % (n+1)
        array[k-1] += (n+1)
    for i in range(1, n+1):
        print(i, array[i-1] // (n+1))


a = [3, 1, 3, 2, 6, 7, 3, 8, 10, 10]
print_frequency(a)

The best solution has already been provided by Venkatesh. The above is a python implementation of the same. Key thing to note is that we know the range of the numbers i.e 1-n and the size of the array i.e. n. So we can use the array as some kinda makeshift hash table.
We iterate through the array and we add (n+1) to the array[item mod n+1]. Basically every time we encounter the number k we add (n+1) to the kth item of the array.
We take the mod to get the original value of k as k would have been modified as result of the above additions.
In the second iteration all we have to do is to divide each item of the array by (n+1) to get the frequency of the index

Clever, but I don't think the problem is fully defined. The size of the array is not specified as size N. If you were guaranteed values 1-n and an array specified as size n, then your solution would work. Still pretty clever.

IS the array sorted??

#include<iostream>
using namespace std;
int main()
{
int a[]={3,3,2,1,1};
cout<<"repeated:"<<endl;
for(int i=0;i<5;i++)
{
if((a[abs(a[i])-1]) > 0)
{
a[abs(a[i])-1]=- a[abs(a[i])-1];

}
else
{
cout<<a[i]<<endl;
}
}
cout<<"missing:"<<endl;
for(int i=0;i<5;i++)
{
if(a[i]>0)
cout<<i+1<<endl;
}
getchar();
return 0;
}

let's consider -
4,3,5,1,2,9,4,2,7,10
n = 10

start iterating the array like count sort with a slight modification that we add n^i to i-th array entry for each occurrence of i in th array- since n is 10 we will add 10^i
so 4,3,5,1,2,9,4,2,7,10 will end up like -
4+10^1, 3+10^2+10^2, 5+10^3, 1+10^4+10^4, 2+10^5, 9+0, 4+10^7, 2+0, 7+10^9, 10+10^10

Now iterate the array from beginning dividing each entry by n^i, result will be the corresponding counts for integer i (0 will be for absent integers) -
for index 1 - 4+10^1 mod 10 ^1 = 1
for index 2 - 3+10^2+10^2 mod 10^2 = 2
and so on
resultant array is -
1,2,1,2,1,0,1,0,1,1
1 is present once, 2 is present twice ...6 and 8 are missing

void process(unsigned long long *arr, int n) {
        unsigned long long   cur, x, y;
        int i;
        for (i = 1; i <= n; i++) {
                cur = *(arr + i -1);
                y = cur % (unsigned long long)pow(n,i);
                x = pow(n,y);
                *(arr + y - 1) += x;
        }   
        for (i = 1; i <= n; i++) {
                cur = *(arr + i - 1); 
                *(arr + i - 1) = cur/pow(n,i);
        }   
        for (i = 1; i <=n ; i++) {
                printf("%d repeated %llu times\n", i, *(arr+i-1));
        }   
}

I used the following algo in my code which the interviewer accepted at once ....

1.Start traversing the array . Let there be n elements and array be a[].
2.if a[a[i]-1] > 0 and a[i] >0 , then make a[a[i]-1] negative . This will help to keep track of absent nodes .
3.else if a[i]>0 and a[a[i]-1] <0 , subtract n from a[a[i]-1] . This will help to keep the count of multiple visited nodes.
4. else if a[i]<0 and a[i] >= -n , subtract n from a[-a[i]-1].
5. else if a[i] < -n , find subtract n from a[ (-a[i])%n-1 ] .
6. Now traverse the list and if any a[idx] is positive , that means number idx+1 isn't present in the array .
7. If a[idx] is between -n to -1 , that means idx+1 has occured only one time .
8. else if a[idx] is less than -n , that means idx+1 has occured ( int ) ( -a[idx]/n ) + 1 times .


P.S. I wasn't selected for the next round after telling this answer within 5 minutes .

Voted up cause the solution is almost correct :) Please see note from <vishnuJayvel>, he is pointing out a very important case handling.

Use hash map.

it takes o(n) time and o(1) space.
Correct me if i made mistake

public static frequency(int arr[])
{
map <Integer> fmap = new Hashmap<Integer>;
for (int a : arr)
{
int freq= fmap.get(a);

if (freq!=null)
{
freq++;
m.put(freq);
}
else			// this is the first time we are encountering the number
{
freq=1;
m.put(freq);
}

}
}

cheers Krishna

A very simple approach :

printAllAbsentNums(int[] a)
{
for(int i=0;i<a.length;i++)
{
temp=a[i];
a[i]=a[temp];
a[temp]=temp;
temp=a[i];
}
for(int i=0;i<a.length;i++)
{
if(a[i]!=i)
	System.out.print(i);

}
}

I think, here we will have to consider n, the upper limit as a constant and m as the input size. In such a case, we can have an auxiliary array of size n that maintains the count of numbers from 1 to n.

The problem can also be solved in O(n) time if the array is already sorted, but not sure if such an assumption can be made.

This problem can be solved in O(1) space and O(n) time, iff the given array is sorted, which is not clear from the question.