Lottery Tickets
Source: codechef
Difficulty: 1520

Lottery Tickets
There were$N$lottery tickets with numbers$A_i$. Each number was distinct. Chef bought the first ticket, i.e.$A_1$.
He is now wondering whether he won the lottery. Here is how the winner is decided:
A number$X$is decided in the range$[1, 10^{6}]$, and then whoever has the closest ticket to$X$wins the lottery. If there is a tie, all of them are winners.
How many numbers$X$exist such that Chef won the lottery?
Input Format
The first line of input will contain a single integer$T$, denoting the number of test cases.
Each test case consists of multiple lines of input.
The first line of each test case contains$N$- the number of sold tickets
The second line of each test case contains$N$integers -$A_1, A_2, ..., A_N$.
Output Format
For each test case, output on a new line the number of integers$X$such that Chef wins the lottery.
Constraints$1 \le T \le 10^4$$2 \le N \le 2 \cdot 10^5$$1 \le A_i \le 10^6$$A_i \ne A_j$for all$i \ne j$The sum of$N$over all test cases does not exceed$2 \cdot 10^5$Sample 1:
Explanation:
Test Case 1
: The valid numbers$X$are$3, 4, 5, 6, 7$and$8$. Note that$3$is winning despite it being a tie between Chef and the person who bought the$2^{nd}$ticket, because in case of a tie all are declared winners.
Test Case 2
: All$X \ge 9$is winning. Since we are told to count in the range$[1, 10^6]$, the answer is all$X$in$[9, 10^6]$which is$999992$.

Sample Input:
3
3
5 1 12
2
10 7
5
3 1 4 5 2

Sample Output:
6
999992
1

C++ solution:
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")

using namespace std;
using namespace __gnu_pbds;

#define ll long long
#define f(i, n) for (ll i = 0; i < n; i++)
#define ia(a, n) \
    ll a[n];     \
    f(i, n) cin >> a[i]
#define iv(v, n)     \
    vector<ll> v(n); \
    f(i, n) cin >> v[i]
#define MOD (1000000007)
#define INF 1000000000000000000LL // Infinity for ll
#define mp make_pair
#define nline '\n'
#define yes cout << "YES\n"
#define no cout << "NO\n"

template <typename T>
using os = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T>
using oms = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

// read question properly
// don't forget newlines!!!!!!
// take care about cin >> t;
// comment the optimization before debugging
// ALWAYS USE FIXED << SETPRECISION WHILE OUTPUTTING FLOATS

void solve()
{
    ll n;
    cin >> n;
    ia(a, n);
    ll k = a[0];
    sort(a, a + n);

    if (n == 1)
    {
        cout << 1000000 << nline;
        return;
    }

    if (a[n - 1] == k)
    {
        ll ans = 0;
        // k to 1e6
        ans += 1000000 - k + 1;
        ans += k - (k + a[n - 2] + 1) / 2;
        cout << ans << nline;
    }
    else if (a[0] == k)
    {
        ll ans = 0;
        // 1 to k
        ans += k;
        ans += (a[1] + k) / 2 - k;
        cout << ans << nline;
    }
    else
    {
        auto it = lower_bound(a, a + n, k) - a;
        ll low = (a[it - 1] + a[it] + 1) / 2;
        ll high = (a[it + 1] + a[it]) / 2;
        cout << high - low + 1 << nline;
    }
}

int main()
{
#ifdef PRADY
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    clock_t T = clock();
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    long long t = 1;
    cin >> t;

    while (t--)
    {
        solve();
    }

#ifdef PRADY
    cout << "\nTime taken: " << ((float)(clock() - T)) / CLOCKS_PER_SEC << " seconds";
#endif
    return 0;
}

Go solution:
package main

import (
    "bufio"
    "fmt"
    "os"
    "sort"
    "strconv"
    "strings"
)

func main() {
    reader := bufio.NewReader(os.Stdin)
    writer := bufio.NewWriter(os.Stdout)
    defer writer.Flush()

    tStr, _ := reader.ReadString('\n')
    t, _ := strconv.Atoi(strings.TrimSpace(tStr))

    for i := 0; i < t; i++ {
        nStr, _ := reader.ReadString('\n')
        n, _ := strconv.Atoi(strings.TrimSpace(nStr))

        vStr, _ := reader.ReadString('\n')
        v := strings.Fields(vStr)
        vInt := make([]int, n)
        for j := 0; j < n; j++ {
            vInt[j], _ = strconv.Atoi(v[j])
        }

        start := vInt[0]
        sort.Ints(vInt)

        if start == vInt[0] {
            fmt.Fprintln(writer, start+(vInt[1]-start)/2)
        } else if start == vInt[n-1] {
            fmt.Fprintln(writer, 1000000-start+1+(start-vInt[n-2])/2)
        } else {
            var a, b int
            for j := 0; j < n; j++ {
                if vInt[j] == start {
                    a = start - (start-vInt[j-1])/2
                    b = start + (vInt[j+1]-start)/2
                    fmt.Fprintln(writer, b-a+1)
                    break
                }
            }
        }
    }
}

Java solution:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;
    
        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
    
        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }
    
        long nextLong() {
            return Long.parseLong(next());
        }
    
        double nextDouble() {
            return Double.parseDouble(next());
        }
    
        String nextLine() {
            try {
                return br.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
    
        String[] nextLineAsStringArray() {
            return nextLine().split(" ");
        }
    
        long[] nextLineAsLongArray() {
            try {
                String line = br.readLine();
                if (line == null || line.isEmpty()) return new long[0];
                StringTokenizer tokenizer = new StringTokenizer(line);
                long[] arr = new long[tokenizer.countTokens()];
                for (int i = 0; i < arr.length; i++) {
                    arr[i] = Long.parseLong(tokenizer.nextToken());
                }
                return arr;
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }


    
    
    

    public static void main(String[] args) {

        FastReader xc = new FastReader();

        int T = xc.nextInt();


       
        

        

        out:

        while(T-->0) {

        int n = xc.nextInt();
         
        int arr[] = new int[n];
 
        int k = xc.nextInt();
        int m =  Integer.MAX_VALUE;

        

        arr[0] = k;
        for(int i = 1; i < n; i++) {
            arr[i] = xc.nextInt();
            

        }

        int wins = 0;
        int iox =  k<=1 ? 0 : k-1;

        Arrays.sort(arr);
        for(int i=0; i<n; i++){
            if(arr[i] == k && i != 0 && i != n-1){
                wins = (k-arr[i-1] )/2 + (arr[i+1] - k )/2;
            }

            else if(arr[i] == k && i == 0){
                wins = (arr[i+1] - k )/2 + iox;
            }

            else if(arr[i] == k && i == n-1){
                wins = (k - arr[i-1] )/2 + (int)Math.pow(10,6) - k;
            }

            



        }



        System.out.println(wins+1);

        
       

        
        
        
        



 
        
            
            
        




        


        
        
        



        


         
}}}

JavaScript solution:
/* -------------------------------------------------------- */
/*   ( The Authentic JS CodeBuff )
 ___ _                      _              _ 
 | _ ) |_  __ _ _ _ __ _ __| |_ __ ____ _ (_)
 | _ \ ' \/ _` | '_/ _` / _` \ V  V / _` || |
 |___/_||_\__,_|_| \__,_\__,_|\_/\_/\__,_|/ |
                                        |__/ 
 */
/* ---------------------------------------------------------   */
/*    Youtube: https://youtube.com/@code-with-Bharadwaj        */
/*    Github : https://github.com/Manu577228                  */
/* ----------------------------------------------------------- */

// Template Starts here Fast IO!

let V8Flags = [
    '--max-old-space-size=4096', '--max-semi-space-size=16', '--stack-size=65536', '--reclaim-unused-memory',
    '--gc-interval=100', '--expose-gc', '--gc-global', '--optimize-for-speed',
    '--always-opt', '--max-inlined-source-size=600', '--max-inlined-bytecode-size=600', '--turbo-inline-js-wasm-calls',
    '--turbo', '--turbo-optimizer', '--force-optimization', '--no-lazy',
    '--no-lazy-inner-functions', '--optimize-for-size', '--initial-heap-size=64', '--max-heap-size=192',
    '--use-strict', '--predictable', '--single-threaded-gc', '--no-inline-new',
    '--opt', '--no-lazy-deserialization', '--no-browser-globals', '--turbo-inline-array-builtins',
    '--fast-math', '--fuzzing', '--minor-mc', '--incremental-marking',
    '--concurrent-recompilation', '--stress-compaction', '--experimental-flush-embedded-blob-icache', '--experimental-value-unavailable'
];

if (V8Flags.length > 0) {
        process.execArgv.push('--v8-options=' + V8Flags.join(' '));
}

let i = Buffer.allocUnsafe(1e7);
let p = 0,
        l = 0;
let o = Buffer.allocUnsafe(1e7);
let q = 0;

let f = require('fs');
l = f.readSync(process.stdin.fd, i, 0, i.length, null);

function r() {
        let n = 0,
                s = 1;
        while (i[p] < 48 || i[p] > 57) {
                if (i[p] === 45) s = -1;
                p++;
        }
        while (p < l && i[p] >= 48 && i[p] <= 57) {
                n = n * 10 + (i[p++] - 48);
        }
        return n * s;
}

let m = true;

function w(v, e = false) {
        if (!m) {
                o[q++] = 32;
        }
        if (v < 0) {
                o[q++] = 45;
                v = -v;
        }
        let d = [];
        do {
                d.push(v % 10);
                v = Math.floor(v / 10);
        } while (v > 0);
        for (let j = d.length - 1; j >= 0; j--) {
                o[q++] = 48 + d[j];
        }
        m = e;
        if (e) {
                o[q++] = 10;
                m = true;
        }
}

// Template Ends here!

let solve = () => {
        let n = r();
        let v = [];
        let s = 0;
        for (let j = 0; j < n; j++) {
                let x = r();
                if (j === 0) s = x;
                v.push(x);
        }
        v.sort((a, b) => a - b);
        if (s === v[0]) {
                w(s + Math.floor((v[1] - s) / 2), true);
        } else if (s === v[n - 1]) {
                w(1000000 - s + 1 + Math.floor((s - v[n - 2]) / 2), true);
        } else {
                let a = 0,
                        b = 0;
                for (let j = 0; j < n; j++) {
                        if (v[j] === s) {
                                a = s - Math.floor((s - v[j - 1]) / 2);
                                b = s + Math.floor((v[j + 1] - s) / 2);
                                break;
                        }
                }
                w(b - a + 1, true);
        }
};

let t = r();
while (t--) solve();
f.writeSync(process.stdout.fd, o.slice(0, q));

Python solution:
# cook your dish here
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    p = a[0]
    a.sort()
    ans = 1
    if a.index(p) == 0 :
        y = a[a.index(p) + 1]
        ans += (y - p) // 2
        ans += p - 1
    elif a.index(p) == n - 1 :
        z = a[a.index(p) - 1]
        ans += (p - z) // 2
        ans += 1000000 - p
    else :
        y = a[a.index(p) + 1]
        z = a[a.index(p) - 1]
        ans += (y - p) // 2
        ans += (p - z) // 2
    print(ans)

Ruby solution:
def solve
  input = $stdin.readlines.map(&:chomp)
  ptr = 0
  t = input[ptr].to_i
  ptr += 1
  t.times do
    while input[ptr].empty?
      ptr += 1
    end
    n = input[ptr].to_i
    ptr += 1
    while input[ptr].empty?
      ptr += 1
    end
    a = input[ptr].split.map(&:to_i)
    ptr += 1
    p = a[0]
    a.sort!
    index = a.index(p)
    
    ans = 0
    
    if index == 0
      # Chef's ticket is the smallest
      y = a[index + 1]
      ans += (y - p) / 2
      ans += p - 1
      ans += 1
    elsif index == n - 1
      # Chef's ticket is the largest
      z = a[index - 1]
      ans += (p - z) / 2
      ans += 1_000_000 - p
      ans += 1
    else
      # Chef's ticket is in the middle
      y = a[index + 1]
      z = a[index - 1]
      ans += (y - p) / 2
      ans += (p - z) / 2
      ans += 1
    end
    
    puts ans
  end
end

solve