Gain insights into competitive programming, explore C++ skills with theory, code samples, practice problems, and master faster implementation for contests like ACM ICPC, Google CodeJam, and HackerCup.

Competitive programming can be a great way to build out your programming skills, get on any major company’s radar, and earn a little extra cash along the way.

In this course, you will learn to prepare for competitive programming contests like ACM ICPC, Google CodeJam, Facebook HackerCup, and many more.

Each topic is broken down with a healthy mix of theory, code samples, step-by-step solved sample problems, illustrations, useful practice problems, and tips and tricks for faster implementation.

You will need some solid C++ foundations coming into this course, but by the end it, you will be confident enough in your C++ skills to take home the win.

Competitive Programming in C++: The Keys to Success

## Problem statement
Given a **sorted** array of $N$ integers $A[]$. Find if there exist a pair of integers $A[i]$ and $A[j]$ such that the sum is equal to the given integer $X$.

**Input format**

The first line of input consists of two space-separated integers $N(1 \leq N \leq 10^{5})$ and $X(1 \leq X \leq 10^{6})$.

The next line contains $N$ space-separated integers representing the array $A[](1 \leq A[i] \leq 10^{5})$.

**Output format**

Print a single line of two space-separated integers $i$ and $j$ such that $A[i] + A[j] = X$ or print $-1$ if there is no such pair.

---

## Sample

**Input**
```
6 14
2 4 7 10 15 16
```

**Output**
```
2 4
```

---

## Explanation

$2^{nd}$ and $4^{th}$ element of $A[]$ add upto $14$.

$A[2] = 4$

$A[4] = 10$

---

## Brute force

Use two loops to iterate over the array and check all ${N} \choose {2}$ pairs. Time complexity is $O(N^{2})$.

---


## Optimization to $O(N)$

Let's see how we can optimize the time, even more, using $2$ pointers. The algorithm is very similar to binary search in terms of how we move the pointers.

We start from the two ends of the sorted array using two pointers lets call the $p$ and $q$. The algorithm:

Compare $A[p] + A[q]$ and $X$:

* If X is equal, we found a pair $A[p],A[q]$.

* If X is greater, move $p$ to $p+1$. This will increase the sum of $A[p] + A[q]$.

* If X is smaller, move $q$ to $q-1$. This will decrese the sum of $A[p] + A[q]$.

# Problem statement
Given a **sorted** array of $N$ integers $A[]$. Find if there exist a pair of integers $A[i]$ and $A[j]$ such that the sum is equal to the given integer $X$.

**Input format**

The first line of input consists of two space-separated integers $N(1 \leq N \leq 10^{5})$ and $X(1 \leq X \leq 10^{6})$.

The next line contains $N$ space-separated integers representing the array $A[](1 \leq A[i] \leq 10^{5})$.

**Output format**

Print a single line of two space-separated integers $i$ and $j$ such that $A[i] + A[j] = X$ or print $-1$ if there is no such pair.

---

# Sample

**Input**
```
6 14
2 4 7 10 15 16
```

**Output**
```
2 4
```

---

# Explanation

$2^{nd}$ and $4^{th}$ element of $A[]$ add upto $14$.

$A[2] = 4$

$A[4] = 10$

---

# Brute force

Use two loops to iterate over the array and check all ${N} \choose {2}$ pairs. Time complexity is $O(N^{2})$.

---


# Optimization to $O(N)$

Let's see how we can optimize the time, even more, using $2$ pointers. The algorithm is very similar to binary search in terms of how we move the pointers.

We start from the two ends of the sorted array using two pointers lets call the $p$ and $q$. The algorithm:

Compare $A[p] + A[q]$ and $X$:

* If X is equal, we found a pair $A[p],A[q]$.

* If X is greater, move $p$ to $p+1$. This will increase the sum of $A[p] + A[q]$.

* If X is smaller, move $q$ to $q-1$. This will decrese the sum of $A[p] + A[q]$.

Introduction

Complexity Analysis

Number Theory

Arrays and Vectors

Sieve of Eratosthenes

Strings

Sorting

Linked List

Stack

Queue

Binary Tree

2 Pointers

Heap

Binary Search Tree

Balanced Binary Search Tree

Course Conclusion

Solved Problem - Pair Sum

Problem statement