CareerCup

Lets say the array has M numbers. For the purpose of this problem, negative values and 0s are irrelevant. Also, numbers larger than M can be treated as M because the answer is never larger than M.

So, we can count the number of existing values between 1 and M. Then, process the values backwards (M to 1) to find the answer, adding the counts of the values processed so far.

This yields an O(M) algorithm with extra O(M) memory.

int Solve(const vector<int>& values) {
	int n = values.size();
	vector<int> count(n+1, 0);
	for (auto val: values)
		if (val >= n)
			count[n]++;
		else if (val > 0) // ignore negative values
			count[val]++;
	int am = 0;
	for (int i = n; i > 0; i--) {
		am += count[i];  // amount of numbers >= i
		if (am >= i)
			return i;
	}
	return 0;
}

M elements, want to find n.

Binary search on n, using selection algorithm.

Guess n = n'. Find the n' largest element K using linear time selection algorithm. Check if K >= n'.

We can ignore half the elements already considered, so O(M) time algorithm.

Sort the array in descending order. Loop over it from the beginning till you find A[i] where i > A[i]. This would be nlog(n).

sort in mlog(m)
then binary search log(m)

Sort the array in descending order. Loop over it from the beginning till you find A[i] where i > A[i]. This would be nlog(n).

int geN(vector<int>& arr)
{
    sort(arr.begin() , arr.end());
    
    int N = arr.size();    
    
    for(int i = N - 1 ; i >= 0 ; --i)
    {
        if(arr[i] <= N - i)
            return arr[i];
    }
    
    return -1000;    
}

int main()
{
   cout <<geN(arr1);
   cout <<"\n"<<geN(arr2);
   
   return 0;
}

Idea: inside the quick sort algorithm iteration process only one "half" of array depending on "pivotValue", length of left and right sub-array.
Pros: in avarage case should be still O(nlogn) but with smaller koefficient
Cons: worst case is still O(n^2)

1. sort the array in ascending order
2. then look for i where n-i+1>=a[i]; if no such element exists, then return 0
3. time complexity o(nlogn)

// Java code

public static int solve(int[] a) { 
    Arrays.sort(a); 
    for (int i = a.length; i > 0 ; i--) { 
        if (a[a.length - i] >= i) 
            return i; 
    } 
    return 0; 
}

import bisect, random

def max_number_possible_n_array(ar):
    """

    :param ar: array
    :return: max possible n such that at least n values >= n
     m = len(ar)
    1. sort the array in ascending order O(m) = m*log(m)
    2. do binary search for the 1st element > O(m) = log(m)
    3. go right from the index and evaluate len(ar)-index (number of elements) >= arr[index] and return the last element find... O(m) = m
    running time m*log(m)
    """
    b = sorted(ar)
    i = bisect.bisect_right(b, 0)
    if i == len(b):
       return -1
    l = len(b)

    while l-i  >= b[i] and i < l:
        i += 1
    return b[i-1]


if __name__ == '__main__':
    print max_number_possible_n_array([1,2,3,4])
    print max_number_possible_n_array( [900, 2, 901, 3, 1000])
    ar = [random.randint(1,100) for x in range(20)]
    v = sorted(ar)
    print v
    print max_number_possible_n_array(ar)

Sort the array in descending order
loop over the element and return the element where A[i] = i

///
import java.util.Arrays;

public class MaxN {

public static int arrayReturn(int[] arr){
Arrays.sort(arr);
int length = arr.length;
int i = length/2-1; //for identifying the position
int howmany = length - i ;
while( i>0 && arr[i] > howmany )
i--;

return arr[i];
}

public static void main(String args[]){
int[] array = {900, 2, 901 , 3, 1000};
int i = arrayReturn(array);
System.out.println(i);
}

}
\\\

This would be my answer :
1. Let the input array be A[] of size M.
2. Sort the array A in ascending order
3. Var N = -1 ( Assuming all elements are positive )
4. for each element A[i] starting from A[M-1] to A[0] do the following:
__4.a. if A[i] <= (M-i-1) : N = A[i] ; Break
5. if N == -1 then " No Results found" else "Answer is "+ N

Analysis :
Sorting : Time :O(M) Counting Sort ( Space Complexity depends on Input range O(A[M-1])
or Time : O(nlogn) and Space : O(1) for heap Sort

Finding the element : Time O(M)
Total : O(M) + O(M) = O(M)

Correct me if i am wrong

Linear time: very simple and obvios modification of quick select

1. Build a TreeMap (Map with sorted keys) and count the frequency of each number
2. Traverse in descending order and sum the frequency of the numbers
3. Stop when sum >= n
O(n log(n)) time
O(n) space

public int solve(int[] array) {
		TreeMap<Integer,Integer> map = new TreeMap<Integer,Integer>();
		for (int i : array) {
			int count = map.containsKey(i) ? map.get(i) : 0;
			map.put(i, count + 1);
		}
		int n = 0;
		for (Entry ent : map.descendingMap().entrySet()) {
			n += (Integer)ent.getValue(); 
			if (((Integer)ent.getKey()).compareTo(Integer.valueOf(n)) < 0) {
				return (Integer)ent.getKey();
			}
		}
		return 0;
	}

N: size of array. O(N) time (amortized), O(1) space. A modification of quicksort like many others pointed out.

(semi rigorous) proof for complexity:
At any stage, T(n) = T(a n) + O(n); a<1 at subproblem size n (i.e., we are depending on a smaller problem of size a N). In reality we will have different values of

a

at every stage but lets say its the average value.
on summing up starting from problem size N, we have N + a N + a^2 N + .... + 1 and termination is upon reaching 1 or 0. so, we have: T(N) = (1-a^(N+1)/(1-a))*N.
when N-<inf, T(N) -> N.

O(1) space because it is in place.

package pracPkg;

import java.util.Arrays;

public class NGreaterThanN {
	public static void main(String[] args){
		int[] arr;
		arr = new int[]{3,2,1,9,8,7};
		//arr = new int[]{1,4,9,8,7,3,5};
		System.out.println(Arrays.toString(arr));
		System.out.println(nGn(arr));
	}
	public static int nGn(int[] arr){
		return nGn(arr, 0, arr.length-1, -1);
	}
	private static int nGn(int[] arr, int start, int end, int bestAns){
		if(end< start)
			return bestAns;
		if(start == end){
			if(arr.length - start >= arr[start])
				bestAns = arr[start];
			return bestAns;
		}
		int ind = partition(arr, start, end);
		if(arr.length - ind >= arr[ind]){
			bestAns = arr[ind];
			return nGn(arr,ind+1,end,bestAns);
		}
		else
			return nGn(arr,start,ind-1,bestAns);
	}
	
	private static int partition(int[] arr, int start, int end){
		int pivot = arr[start];
		int i = start, j= start+1;
		while(j<=end){
			if(arr[j]<pivot){
				int temp = arr[i+1];
				arr[i+1] = arr[j];
				arr[j] = temp;
				i++;
			}
			j++;
			int temp = arr[i];
			arr[i] = pivot;
			arr[start] = temp;
			
		}
		return i;
	}

}

#include <iostream>

int findNthN(int *arr, int n){
  std::map<int, int> map1;
  for (int i=0; i<n; i++){
    if (!map1[arr[i]]){
      map1[arr[i]] = 1;
    } else {
      map1[arr[i]] += 1;
    }
  }
  for (int i=0; i<n; i++){
    if (map1[arr[i]] == arr[i]){
      return arr[i];
    }
  }
  return NULL;
}

How about this?
I can solve without extra storage.

1. First, I will do quick select for the median position.
2. See the left side of median to find maximum candidate.

1 will take 2n on the vatage, 2 will take n, so total 3n, leading O(n).

public static Result findMax_N_Num_HavingMorethanOrEqual_N_Num_in_unsortedArray(int[] arr) {
    validateArray(arr);
    assert(arr.length >= 2);
    int halfLen = arr.length/2 + arr.length%2;
    int medianIndex = quickIndexSelect(arr, halfLen);
    int maxNum = 0;
    boolean isFound = false;
     
    for (int i = medianIndex; i >=0; i--) {
      if (arr[i] <= (halfLen)) {
        isFound = true;
        maxNum = Math.max(maxNum, arr[i]);
      }
    }
    return new Result(isFound, isFound ? maxNum : null);
  }

private static class Result {
    private final boolean isFound;
    private final Integer num;
     
    private Result(boolean isFound, Integer num) {
      this.isFound = isFound;
      this.num = num;
    }
  }

1. use linear select to find the middle element.
2. check if middle element X <= N - m.
here m is the absolute postion of the original array but middle position of the subarray.
if true
search on right.
else
search on left

binary search and linear select
1. use linear select to find the middle element.
2. check if the middle element value is less then or equal to the number of elements on the right side of the original array not in the subarray.

public class Test {

public static int getNumber(int[] A) throws Exception {
int result = helper(A, 0, A.length - 1, 0);
if (result == 0)
throw new Exception("Number does not exist!");
return A[A.length - result];
}

// return the num of elements which is greater to equal to the pivot
public static int helper(int[] A, int start, int end, int tailSize) {
if (start > end)
return 0;

// choose the starting number of this range as pivot
int left = start, mid = start + 1, right = end;
while (mid <= right) {
if (A[mid] < A[left]) {
swap(A, left, mid);
mid++;
left++;
} else if (A[mid] == A[left])
mid++;
else {
swap(A, mid, right);
right--;
}
}

int greaterOrEqualToPivot = end - left + 1 + tailSize;
if (greaterOrEqualToPivot >= A[left]) {
int subResult = helper(A, right + 1, end, tailSize);
if (subResult != 0)
return subResult;
else
return greaterOrEqualToPivot;
} else
return helper(A, start, left - 1, greaterOrEqualToPivot);
}

public static void swap(int[] A, int left, int right) {
int temp = A[left];
A[left] = A[right];
A[right] = temp;
}

public static void main(String[] args) throws Exception {
System.out.println(getNumber(new int[] { 900, 2, 901, 3, 1000 }));
}

}

The number should be part of Array or it can be other number otoo.

import java.lang.Integer;

public class HighestNumArray {

	public static int highChecker(int[] a) {
		int length = a.length;
		int count = 0;
		
		if (a.length==0)return Integer.MIN_VALUE;
		
		int thenum = Integer.MIN_VALUE;
		for (int i = 0; i < length; i++) {
			count = 0;
			for (int j = 0; j < length; j++) {
				if (j == i)
					continue;
				if (length - a[i] > 0) {
					if (a[i] < a[j]) {
						count++;
						if (count == a[i] && a[i] > thenum) {
							thenum = a[i];
							break;
						}

					}

				}
			}
		}
		return thenum;
	}

	public static void main(String[] args) {
		int[] a = new int[] { 900, 2, 901, 3, 1000, 50, 60, 12, 34, 45, 56, 7,
				7, 3, -1, -2, 8 };
		System.out.println((highChecker(a)==Integer.MIN_VALUE)?"Not value":highChecker(a));

	}

}

O(n) time & O(n) space:

1. build max-heap
2.init count = 0 && n = max_int;
while count<n : delete max from the heap + update n by max value, update count.

int chr[6] = { 9, 15, 11, 7, 2, 4 };

//return 0;


int i, j, tmp;

int len = sizeof(chr) / sizeof(*chr);


for (i = 1; i < len; i++)
{
j = i;
while (j > 0 && chr[j - 1] > chr[j])
{
tmp = chr[j];
chr[j] = chr[j - 1];
chr[j - 1] = tmp;
j--;
}

}

tmp = 0;

for (i = 1; i < len; i++)
{
if ((chr[i] >= (len - chr[i])) && ((len - chr[i]) > 0) )
tmp = chr[i];
//return 0;
}

cout << tmp << endl;

int main() {
	string s = "moss wasgreatman a great mawasgreatmann";
	string t[3] = { "was", "great", "manxxx" };
	bool blnMatch = true;
	int len = sizeof(t) / sizeof(*t);

	for (int i = 0; i < len; i++) //iterate through array of substrings
	{
		for (int j = 0; j < s.length(); j++) //check for start in long string
		{
			if (t[i][0] == s[j])
			{
				blnMatch = true; // initialize boolean
				for (int x = 1; x < t[i].length(); x++) //Loop through substring, matching letters in both strings.
				{
					if ((s[j + x] != t[i][x]))
						blnMatch = false; //sets flag to false when no match.
				}
			}

			if ((j >= (s.length() - t[i].length()) - 1) && (blnMatch == false)) // if end of string and no match, prints.
			{
				cout << t[i] << ": substring not found" << endl;
				break;
			}
		}
		
	}
	
}

I tried in Java and check with different types of the input and it returns correctly.
Can someone help me with runtime complexity of this program?

public static void main(String[] args) {
		
//		int[] inputArray = {1,2,3,4};
//		int[] inputArray = {27,9,13,3,5,2};
//		int[] inputArray = {4,4,4,4,4};
//		int[] inputArray = {4,4,4};
//		int[] inputArray = {901,909,905,899};
//		int[] inputArray = {900, 2, 901, 3, 1000};
		int[] inputArray = {1,4,2,1};
		
		int res = solve(inputArray);
		System.out.println("res: " + res);
	}
	
	private static int solve(int[] in) {
		int max = -1;													//max=-1
		int size = in.length;											//size=4
		
		for(int i=0; i<in.length; i++) {
			int cnt = 0;												//cnt=0		| cnt=0
			if(in[i] <= size) {											// 1<4		| 2<4
				for(int j=0; j<in.length; j++) {
//					System.out.println("i,j : "+ in[i] + " "+ in[j]);
					if(in[i] <= in[j]) {								// 1>=1		| 2>=1	2>=2	2>=3
						cnt++;											// cnt=1	| 		cnt=1
//						System.out.println("cnt: " + cnt);

						if(cnt == in[i] && in[i] > max) {				// 1==1&1>-1|		1=2
							max = in[i];								// max = 1	|		
//							System.out.println("max1: " + max);
							break;
						}
					}
				}
//				System.out.println("\n");
			}
		}
		return max;
	}

Best method:

1.Sort the array in descending order.
2.Find n @A[i]
3.If i<(m-n+1)
4. Output values A[i] toA[m-n+1]
5.Else no output

Complexity would still be O(nlogn)

Seems like the h-index calculation. Can be done in O(logn) on sorted array

function nGreaterThanN(arr) {
  var max = arr.length;
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] < max) {
      max--;
    }
  }
  return max;
}

static public int findnum(int [] a){
int l = a.length;
int t = a[1];
for(int i=0; i<l; i++){
if(a[i]<l){
if(t<a[i])
t = a[i];
}
}
return t;
}

int Solve(vector<int> input )
{
	int result = input.size() ;
	
	for ( int i = 0 ; i < input.size() ; ++i )
	{
		if ( input[i] < result ) --result ;
	}
	
	return result ;
}

public class MaximumPossible {

    public static void solve (int [] input){
        Arrays.sort(input);
        int length = input.length - 1;
        List<Integer> temp = new ArrayList<>();

        for(int i = 0; i<=length; i++){
            if(input[i] <= length-i){
                temp.add(input[i]);
            }
        }

        System.out.println(findMax(temp));
    }

    private static int findMax(List<Integer> temp) {
        if(temp.isEmpty()) return 0;
        int max = temp.get(0);
        for(int i = 1 ; i<temp.size() ; i++){
            if(max < temp.get(i)){
                max = temp.get(i);
            }
        }
        return max;
    }

    public static void main(String[] args) {
        int[] input = {1,4,2,1};
        MaximumPossible.solve(input);
         input = new int[]{1, 2, 3, 4};
        MaximumPossible.solve(input);
         input = new int[]{900, 2, 901, 3, 1000};
        MaximumPossible.solve(input);
        input = new int[]{900, 902, 901, 903, 1000};
        MaximumPossible.solve(input);
    }
}