The first line gives n and S; the second line gives n integers a₁ … aₙ sorted in non-decreasing order (equal values allowed). Find positions i < j with aᵢ + aⱼ = S and print "i j" (positions start at 1). The same position cannot be used twice. If there are several answers, print the one with the smallest i, and among those the largest j. If no such pair exists, print -1.
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
Trying every pair takes about 50 million steps when n = 10,000, which is slow. Because the list is sorted, use two pointers: start at both ends and move the left one right when the sum is too small, the right one left when it is too big; that finishes within n steps. It also naturally finds the answer with the smallest i and then the largest j first. The answer has two values (i, j), and returning two values from a function differs by language: a Python tuple return i, j, a JavaScript array return [i, j] with const [i, j] = …, a TypeScript tuple type [number, number], a C# tuple (int, int) with var (i, j) = …, C++ std::pair with auto [i, j] = …, Java has no tuples so int[] (or a record), C uses pointer parameters int *pi, and Craykon returns a list return [i, j];. Two traps: looping while lo <= hi uses one element twice and finds 5 + 5 = 10 in 1 5 9. And values go up to 2 billion, so a sum of two can exceed int (about 2.1 billion) — C, C++, Java and C# must read them as long long/long (Java and C# wrap around to a negative number; in C and C++ signed overflow is undefined behavior, so it may or may not give the right answer), while Python, JavaScript, TypeScript and Craykon are fine as is.
Pythonmain.py · 18 lines
def find_pair(a, s): """a[i] + a[j] == s 인 (i, j)를 1부터 센 자리로 돌려준다. 없으면 (-1, -1).""" lo, hi = 0, len(a) - 1 while lo < hi: total = a[lo] + a[hi] if total == s: return lo + 1, hi + 1 if total < s: lo += 1 else: hi -= 1 return -1, -1n, s = map(int, input().split())a = list(map(int, input().split()))i, j = find_pair(a, s)print(-1 if i == -1 else f"{i} {j}")
JavaScriptmain.js · 16 lines
// a[i] + a[j] === s 인 [i, j]를 1부터 센 자리로 돌려준다. 없으면 [-1, -1].function findPair(a, s) { let lo = 0; let hi = a.length - 1; while (lo < hi) { const total = a[lo] + a[hi]; if (total === s) return [lo + 1, hi + 1]; if (total < s) lo++; else hi--; } return [-1, -1];}const [n, s, ...a] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [i, j] = findPair(a, s);console.log(i === -1 ? "-1" : `${i} ${j}`);
TypeScriptmain.ts · 18 lines
import { readFileSync } from "node:fs";// a[i] + a[j] === s 인 [i, j]를 1부터 센 자리로 돌려준다. 없으면 [-1, -1].function findPair(a: number[], s: number): [number, number] { let lo = 0; let hi = a.length - 1; while (lo < hi) { const total = a[lo] + a[hi]; if (total === s) return [lo + 1, hi + 1]; if (total < s) lo++; else hi--; } return [-1, -1];}const [n, s, ...a]: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [i, j] = findPair(a, s);console.log(i === -1 ? "-1" : `${i} ${j}`);
JavaMain.java · 30 lines
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { // a[i] + a[j] == s 인 {i, j}를 1부터 센 자리로 돌려준다. 없으면 {-1, -1}. static int[] findPair(long[] a, long s) { int lo = 0, hi = a.length - 1; while (lo < hi) { long total = a[lo] + a[hi]; if (total == s) return new int[] {lo + 1, hi + 1}; if (total < s) lo++; else hi--; } return new int[] {-1, -1}; } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); int n = Integer.parseInt(st.nextToken()); long s = Long.parseLong(st.nextToken()); st = new StringTokenizer(in.readLine()); long[] a = new long[n]; for (int k = 0; k < n; k++) a[k] = Long.parseLong(st.nextToken()); int[] p = findPair(a, s); System.out.println(p[0] == -1 ? "-1" : p[0] + " " + p[1]); }}
C#Main.cs · 27 lines
using System;using System.Linq;class Program{ // a[i] + a[j] == s 인 (i, j)를 1부터 센 자리로 돌려준다. 없으면 (-1, -1). static (int, int) FindPair(long[] a, long s) { int lo = 0, hi = a.Length - 1; while (lo < hi) { long total = a[lo] + a[hi]; if (total == s) return (lo + 1, hi + 1); if (total < s) lo++; else hi--; } return (-1, -1); } static void Main() { long s = long.Parse(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries)[1]); long[] a = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(long.Parse).ToArray(); var (i, j) = FindPair(a, s); Console.WriteLine(i == -1 ? "-1" : $"{i} {j}"); }}
C++main.cpp · 26 lines
#include <iostream>#include <utility>#include <vector>// a[i] + a[j] == s 인 {i, j}를 1부터 센 자리로 돌려준다. 없으면 {-1, -1}.std::pair<int, int> findPair(const std::vector<long long>& a, long long s) { int lo = 0, hi = static_cast<int>(a.size()) - 1; while (lo < hi) { long long total = a[lo] + a[hi]; if (total == s) return {lo + 1, hi + 1}; if (total < s) lo++; else hi--; } return {-1, -1};}int main() { int n; long long s; std::cin >> n >> s; std::vector<long long> a(n); for (auto& x : a) std::cin >> x; auto [i, j] = findPair(a, s); if (i == -1) std::cout << "-1\n"; else std::cout << i << " " << j << "\n";}
Cmain.c · 28 lines
#include <stdio.h>/* 값 두 개는 포인터로 돌려준다. 찾으면 1, 없으면 0. */static int find_pair(const long long *a, int n, long long s, int *pi, int *pj) { int lo = 0, hi = n - 1; while (lo < hi) { long long total = a[lo] + a[hi]; if (total == s) { *pi = lo + 1; *pj = hi + 1; return 1; } if (total < s) lo++; else hi--; } return 0;}int main(void) { static long long a[10000]; int n, i, j; long long s; scanf("%d %lld", &n, &s); for (int k = 0; k < n; k++) scanf("%lld", &a[k]); if (find_pair(a, n, s, &i, &j)) printf("%d %d\n", i, j); else puts("-1"); return 0;}
Craykonmain.cray · 36 lines
// a[i] + a[j] == s 인 [i, j]를 1부터 센 자리로 돌려준다. 없으면 [-1, -1].짝찾기(a, s){ lo = 0; hi = a.Count - 1; while (lo < hi) { total = a[lo] + a[hi]; if (total == s) { return [lo + 1, hi + 1]; } if (total < s) { lo += 1; } else { hi -= 1; } } return [-1, -1];}첫줄 = Console.ReadNumbers();s = 첫줄[1];a = Console.ReadNumbers();답 = 짝찾기(a, s);if (답[0] == -1){ Console.WriteLine(-1);}else{ Console.WriteLine(답[0] + " " + 답[1]);}