Find the kth largest element in an array after inserting the absolute difference back in the array

The answer is equal to m - k + 1 multiplied by the greatest common divisor (GCD) of the elements in the input array, where m is the number of elements in the final array, so long as this number is at least k.

To show this, we need to show that the array after applying the operation as many times as possible will always result in an array of the form [d, 2*d, 3*d, ..., m*d] in some order, where d is the GCD and m is some positive integer. There are three parts to the proof:

• We need to show that d is constructible by some sequence of applying the operation. This is true because the operation allows us to do any subtractions we like where the smaller number is the one subtracted, and this is sufficient to perform Euclid's algorithm.
• We need to show that all of the numbers in the claimed result are constructible. This is true because the largest number in the input array has d as a divisor by definition, so it must be m*d for some m, the smaller multiples can be constructed by repeatedly subtracting d.
• We need to show that no other numbers are constructible. This is true because the result of a subtraction always shares common divisors with the two operands, and because larger numbers cannot be constructed by subtraction.

So the algorithm works as follows:

1. Find the GCD of the input array (e.g. by repeatedly applying Euclid's algorithm). Call the result d.
2. Find the maximum element of the input array, and divide it by d. Call the result m.
3. If m >= k, then return (m - k + 1)*d, otherwise raise an error.

The m - k + 1 term is to get the kth largest element in the result; if the kth smallest element is required, this will be k*d.

Not a complete answer, just some thoughts that might help.

We have streams of numbers. For example, given [2, 4, 9], we know all numbers with the difference of 2 will be generated down from each number, m, higher than 2, as well as m mod 2, which starts another cycle.

9-2=7
7-2=5
5-2=3
etc.

We get [2, 3, 4, 5, 7, 9] and the remainder 1. But 1, using the same procedure, will generate all numbers in the range (1, max).

I would start with considering how to obtain the smallest such remainder (greater than zero) we can have. But we may also need to consider the full range of differences that each generate such a "stream."

import java.util.*;


class TestClass {
    public static void main(String args[] ) throws Exception {
       Scanner s = new Scanner(System.in);
       int t = s.nextInt();
       while(t--!=0){
           int n = s.nextInt();
           int arr[] = new int[n];
           int min = Integer.MAX_VALUE;
           int max = Integer.MIN_VALUE;
           int k;
           for(int i=0;i<n;i++){
             arr[i] = s.nextInt();
             if(arr[i] > max)
                max = arr[i];
             if(arr[i] < min)
                min = arr[i];
             }
             k = s.nextInt();
             int is_dev = 1;
             for(int i =0 ;i < n;i++){
                 if(arr[i]%min !=0){
                     is_dev = 0; //easily reach to [1,2,3 .... max]
                     break;
                 }
             }
            
             if(is_dev == 0){
                n = max - (k - 1);
             } else {
                 n = max - min*(k-1);
             }
             if(n<=0)
              System.out.println("-1");
             else
              System.out.println(n);

           }
            

       }
}

eg1 . 4 7 9 here min - 4 max - 9

if we check all number not divisible to 4 take min number always

iteration 1 . 4 5 7 9 - for pair (4,7) iteration 2 . 1 4 5 7 9 - for pair (4,5) at this point if we have we can easily go upto 1 2 3 4 5 6 7 8 9 easily find kth largest element

so point is any one of number not divisible to min number then we can easily reach to 1.

eg2 . 3 9 min 3 max 9

here all number number divisible by 3 so final array like . 3 6 9

kth largest element will be : max-3(k-1) eg 9 - 3(2-1) =6