instagram

Algorithm of n integers which can contain integers from 1 to n with repeated and absent

You are given an array of n integers which can contain integers from 1 to n only . Some elements can be repeated multiple times and some other elements can be absent from the array . Write a running code on paper which takes O(1) space apart from the input array and O(n) time to print which elements are not present in the array and the count of every element which is there in the array along with the element number .
NOTE: The array isn't necessarily sorted.

Input :
int a[] = { 2, 2, 3, 3, 5 };

Output :
1 : 0
2 : 2
3 : 2
4 : 0
5 : 1

package com.omt.learn.algo;

import java.util.Arrays;

public class NIntegersAmazon {

	public static void main(String[] args) {

		int i = 1;
		int a[] = { 2, 2, 3, 3, 5 };
		calculateDuplicate(a, 5);
		for (int n : a) {
			System.out.println((i) + " : " + Math.abs(n));
			i++;
		}

	}

	public static void calculateDuplicate(int[] a, int n) {

		Arrays.sort(a);

		int currentPosition = 0;
		int validPosition = 0;
		while (currentPosition < n) {

			if (a[currentPosition] <= 0) {
				currentPosition++;
				continue;
			}

			validPosition = a[currentPosition] - 1;
			if (a[validPosition] > 0) {
				a[currentPosition] = a[validPosition];
				a[validPosition] = -1;
			} else {
				a[currentPosition] = 0;
				a[validPosition]--;
				currentPosition++;
			}

		}

	}

}
Share