Find Number Which Is Greater Than or Equal to N in an Array

Find number which is greater than or equal to N in an array

<?php
function closest($array, $number) {

    sort($array);
    foreach ($array as $a) {
        if ($a >= $number) return $a;
    }
    return end($array); // or return NULL;
}
?>

How to find the rightmost number in the array which is greater or equal to current one in O(N) time?

The two problems of finding leftmost and rightmost j for a given i are not symmetrical, because of the added constraint of i < j. When I'm talking about these two tasks I assume that the constraint i < j is not flipped. This constraint means, that we always look to the right of i when searching for j, whether we're looking for rightmost or leftmost j. Without this constraint two tasks would be symmetrical.

---

1. Finding rightmost j, such that i < j and nums[i] ≤ nums[j]

One way to solve this task, is to traverse nums from right to left and maintain the strictly increasing subsequence of already visited elements (with their indices). Current element is added to the sequence only if it's larger, than the largest element already present in the sequence. Adding new element into the sequence is O(1).

For each element of nums you have to perform binary search in the subsequence of the visited elements to find the value that is larger or equals than the current element. Binary search is O(log n).

The total time is O(n log n), the auxiliary space needed is O(n).

Here is the graphical representation of the problem:

Here yellow dots represent the elements that form strictly increasing sequence (and their answer will be -1). Every other element (in blue) picks one of the ranges formed by yellow elements.

---

2. Finding leftmost j, such that i < j and nums[i] ≤ nums[j]

This problem, as opposed to the previous one, can be solved in O(n) time and O(n) space using monotonic stack. Similar to the previous problem, as you traverse nums from right to left, you form and maintain a monotonic stack, but, importantly, when new element is added to the stack all elements that are smaller are removed from the stack. And instead of using binary search to find the larger element, the answer is right at the new top of the stack (after all smaller elements were removed). This makes updating the stack and finding the answer for each element amortized O(1).

Here yellow elements represent elements with answer = -1, when they were added to the stack, they emptied the stack completely, as they were larger than every other element in the stack.

How can I find the largest number in an array that is less than or equal to a random integer?

First, need to claify somethings:
1) the for loop for creating a random number is useless since count is always is one
2) n should not be a parameter for the function since you generate a random number in the function
3) the i should start from 0, starting from 2 doesn't make any sense to me. You’re just wasting the first two elements in the array

Largest is the variable that carries the value of the largest element and still smaller than n.

int Largest = fibArray[0];
for(int counter=1; counter<25; counter++){
    if(fibArray[counter]>Largest && fibArray[counter]<n)
        Largest = fibArray[counter];
}
return Largest;

Is there an O(n) algorithm to find the first missing number in an array?

Given an array of n integers, without negative numbers, not
necessarily sorted, is there an O(n) algorithm to find the least
integer that is greater than the minimum integer in the array but that
is not in the array?

This can be solved with O(N) time complexity, with N being the number of element in the array. Let us call that array a1, the algorithm is as follows:

1. Find the smallest value in a1 (i.e, min);
2. Create a new array a2 with size equals to N;
3. Initialized the array a2 with a value to signal missing element, for instance min - 1;
4. Iterate through the array a1, and for each position, take the element in that position e1 = a1[i], and only if e1 is not greater than min - N mark the corresponded position on a2 as visited, for instance using the element itself, namely a2[e1 - min] = e1; If e1 is greater than min - size then it clearly does not belong to the sequence, and can be ignored because in the worst-case scenario the first missing value will be the value min + N + 1.
5. Lastly, iterate through the array a2, and get the first element = -1; it will be your first missing element.

Steps 1, 3, 4, and 5, all of them take in the worst-case scenario N. Hence, this algorithm takes 4N, which is O(N) time complexity;

The code will be straight forward to implement; for instance something as follows (for an array {5, 3, 0, 1, 2, 6}):

#include <stdio.h>
#include <stdio.h>
#include <stdlib.h>

int find_min(int *array, int size){
    int min = array[0];
    for(int i = 0; i < size; i++)
        min = (array[i] < min) ? array[i] : min;
    return min;
}

void fill_array(int *array, int size, int missing_value){
     for(int i = 0; i < size; i++)
        array[i] = missing_value;
}

void mark_existing_values(int *s, int size, int *d, int min){
    for(int i = 0; i < size; i++){
        int elem = s[i];
        if(elem - min < size)
           d[elem - min] = elem;
    }
}

int find_first_missing_value(int *array, int size, int min){
     int missing_value = min - 1;
     for(int i = 0; i < size; i++){
         if(array[i] == missing_value){
            return i + min;
         }
     }
    return missing_value;
}

int main(){
    int array_size =  6;
    int array_example [] = {5, 3, 0, 1, 2, 6};
    int min = find_min(array_example, array_size);
    int *missing_values = malloc(array_size * sizeof(int));
    fill_array(missing_values, array_size, min - 1);
    mark_existing_values(array_example, array_size, missing_values, min);
    int value = find_first_missing_value(missing_values, array_size, min);
    printf("First missing value {%d}\n", value);
    free(missing_values);
    return 0;
}

OUTPUT:

First missing value {4}

This algorithm works also for negative numbers, for instance if int array_example [] = {-1, -3, 0, 3, 5, 6, 7, 8, 10};, then the output would be:

First missing value {-2}    

The code can be simplified if in step 3 and step 4 instead of min - 1 and a2[e1 - min] = e1, respectively, we use two flags to signal missing (e.g., 0) and existing values (e.g., 1). Just like showcase in @Damien code. The downside is that we are using two flags instead of one. The benefit is that it simplifies the code, and in case the smallest value in the array is the smallest value that can be represented in C we will not underflow with min - 1.

How to find numbers in an array that are greater than, less than, or equal to a value?

I assume this is a homework question so I won't give you a straight code answer but try to help anyways.

System.out.println("Numbers less than 5: ");
for(int x = 0; x < numbers.length && x > 5;) {
    numbers[x] = x + 1;
}

The counting for-loop statement generally consists of three parts (separated by ";"):

1. A variable declaration that is executed before the loop starts, usually a counting variable (in your case "int x = 0")
2. A break condition, if it's true we exit the loop, this is where your loop is wrong (Also your code says "x > 5" which means "x is greater than 5", contradicting your output saying "less than 5").
3. Something that happens after each iteration, usually adding 1 to the count variable defined in the first step (you're missing this in your current code)

When iterating over an array and trying to find elements that match a specific criteria (in this case "number less than 5") you should not do that in the loop condition (step 2 above), if this is true for any one number in your array the loop will stop executing. You should probably check that with an if-statement inside your loop.

for (int x = 0; x < numbers.length; x++) {
    if (/* number is less than 5 */) {
        // print number
    }
}

Now we have a for-loop that will go over the whole array by counting x from 0 (1st part of the for-statement, "int x = 0") until we reach the end of the array (2nd part, "x < numbers.length") in steps of 1 (3rd part, "x++". Could also be written as "x = x + 1"). In each iteration we can now check the element of the array (numbers[x]) for being less than 5 with an if-statement, and if it is print it.

Find how many numbers are greater than N in an array

Try this code:

function findGreaterNumberCount($array, $number) {
    $count = 0;
    foreach ($array as $value) {
        if ($value > $number) {
            $count++;
        }
    }
    return $count;
}

echo findGreaterNumberCount(array(2, 12, 23, 34, 36, 36, 36, 56), 30);

This platform doesn't recommend to write code. So you should try something before asking a question. Be careful next time.

---

Related Topics