Sum of nearest smaller and greater number


Problem Statement

In this question find the sum of nearest smaller and greater number problem, we have given an unsorted array, you have to find two numbers from an array that are just smaller than a number X and just greater than a number X and then add these two numbers.

The Floor denotes the nearest smaller element and Ceil denotes the nearest greater element.

Input Format

First-line containing two integer values N and X.

Second-line containing Sum of nearest smaller and greater number.

Output Format

Print sum of nearest smaller and greater number. If there is no number greater than X then print “No floor of x found” in the position of the first integer. If there is no number smaller than X then print “No ceil of x found” in the position of the second integer.

Constraints

  • 1<=N<=100000
  • -1e9<=X<=1e9
  • -1e9<=a[i]<=1e9 where a[i] denotes the element of the given array.

Algorithm

1. Initialize two variables just_greater and just_smaller with some very large and small value respectively.

2. Loop through the array as:

  • If the array element is greater than x but smaller than just_greater then just_greater = arr[i]
  • If the array element is smaller than x but larger than just_smaller then just_smaller = arr[i]

3. Print Sum of nearest smaller and greater number.

Note: It is simply the modification of finding the second minimum and maximum in an array with a variation of having a reference number with respect to which it is found.

Implementation

C++ Program for Sum of a nearest smaller and greater number

#include <bits/stdc++.h>

using namespace std;
int main() {
    cout << "Enter Count ";
    int n, x;
    cin >> n >> x;
    cout << "Count is " << n;
    cout << "Number is " << x;
    long long int arr[n];
    cout << "Enter Numbers ";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    cout << "Output is ";
    int just_greater = INT_MAX, just_smaller = INT_MIN;
    for (int i = 0; i < n; i++) {
        //if element is greater than x but smaller than present just_greater
        if (arr[i] > x and arr[i] < just_greater)
            just_greater = arr[i];

        //if element is Smaller than x but smaller than present just_smaller
        if (arr[i] < x and just_smaller < arr[i])
            just_smaller = arr[i];
    }
    if (just_smaller == INT_MIN)
        just_smaller = 0;
    if (just_greater == INT_MAX)
        just_greater = 0;
    cout << just_smaller + just_greater;
    return 0;
}

Java Program for Sum of a nearest smaller and greater number

import java.util.Scanner;
public class Main
{
  
  public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        System.out.println("Enter Count ");
        int n = sr.nextInt();
        int x = sr.nextInt();
        System.out.println("Count is " + n);
        System.out.println("Number is " + x);
        int arr[] = new int[n];
        System.out.println("Enter Numbers ");
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        }
        System.out.println("Output is ");
        int just_greater=10000000,just_smaller=-10000000;
        for(int i=0; i<n; i++)
        {
          //if element is greater than x but smaller than present just_greater
          if(arr[i] > x && arr[i] < just_greater)
            just_greater = arr[i];
          //if element is Smaller than x but smaller than present just_smaller
          if(arr[i] < x && just_smaller < arr[i])
            just_smaller = arr[i];
        }   
        if(just_smaller == -10000000)
          just_smaller = 0;
        if(just_greater == 10000000)
          just_greater = 0;
        System.out.println(just_smaller + just_greater);
    }
}

 

Enter Count 
8 0
Count is 8
Number is 0
Enter Numbers 
-3 -4 10 0 3 -2 15 3
Output is 
1

Complexity Analysis

Time Complexity

O(N) where N is the size of the given array. We just traverse the whole array and store the nearest smaller and greater element of X.

Space Complexity

O(1) here we simply use the minimum and maximum conditions wisely.

Conclusion

For any questions like below, the same solution can be used

  • array operations sum of nearest smaller and greater number
  • sum of nearest smaller and greater number program
  • for each element of the array, find the sum of the nearest smaller and nearest greater numbers.
  • sum of nearest smaller and greater number in java

References