# Count of distinct pair sum between two 1 to N value Arrays

Given a positive integer **N** such that there exists two arrays **a[]** and **b[]** each containing values {1, 2, 3, .., N}, the task is to find the count of all pairs (a[i], b[j]) such that a[i] + b[j] is unique among all the pairs i.e. if two pairs have equal sum then only one will be counted in the result.**Examples:**

Input:N = 2Output:3Explanation:

a[] = {1, 2}, b[] = {1, 2}

The three possible pairs are (a[0], b[0]), (a[1], b[0]) and (a[1], b[1]).

Pair 1: 1 + 1 = 2

Pair 2: 2 + 1 = 3

Pair 3: 2 + 2 = 4Input:N = 3Output:5

a[] = {1, 2, 3}, b[] = {1, 2, 3}

The possible pairs with distinct sum are:

Pair 1: 1 + 1 = 2

Pair 2: 2 + 1 = 3

Pair 3: 2 + 2 = 4

Pair 4: 3 + 2 = 5

Pair 5: 3 + 3 = 6

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the

DSA Self Paced Courseat a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please referComplete Interview Preparation Course.In case you wish to attend

live classeswith experts, please referDSA Live Classes for Working ProfessionalsandCompetitive Programming Live for Students.

**Naive approach:**

To solve the problem mentioned above, the naive approach is to to use to a Set to store distinct sums of {1, 2, 3, .. N} and {1, 2, 3, .. N} by using two loops.

Below is the implementation of above approach:

## C++

`// C++ implementation to count` `// of distinct pair sum between` `// two Array with values 1 to N` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to find the distinct sums` `int` `findDistinctSums(` `int` `n)` `{` ` ` `// Set to store distinct sums` ` ` `set<` `int` `> s;` ` ` `for` `(` `int` `i = 1; i <= n; i++) {` ` ` `for` `(` `int` `j = i; j <= n; j++) {` ` ` `// Inserting every sum` ` ` `s.insert(i + j);` ` ` `}` ` ` `}` ` ` `// returning distinct sums` ` ` `return` `s.size();` `}` `// Driver code` `int` `main()` `{` ` ` `int` `N = 3;` ` ` `cout << findDistinctSums(N);` ` ` `return` `0;` `}` |

## Java

`// Java implementation to count` `// of distinct pair sum between` `// two Array with values 1 to N` `import` `java.util.*;` `class` `GFG{` `// Function to find the distinct sums` `static` `int` `findDistinctSums(` `int` `n)` `{` ` ` ` ` `// Set to store distinct sums` ` ` `HashSet<Integer> s = ` `new` `HashSet<>();` ` ` `for` `(` `int` `i = ` `1` `; i <= n; i++)` ` ` `{` ` ` `for` `(` `int` `j = i; j <= n; j++)` ` ` `{` ` ` ` ` `// Inserting every sum` ` ` `s.add(i + j);` ` ` `}` ` ` `}` ` ` ` ` `// Returning distinct sums` ` ` `return` `s.size();` `}` `// Driver code` `public` `static` `void` `main(String[] args)` `{` ` ` `int` `N = ` `3` `;` ` ` `System.out.print(findDistinctSums(N));` `}` `}` `// This code is contributed by gauravrajput1` |

## Python3

`# Python3 implementation to count` `# of distinct pair sum between` `# two Array with values 1 to N` `# Function to find the distinct sums` `def` `findDistinctSums(n):` ` ` `# Set to store distinct sums` ` ` `s ` `=` `set` `()` ` ` `for` `i ` `in` `range` `(` `1` `, n ` `+` `1` `):` ` ` `for` `j ` `in` `range` `(i, n ` `+` `1` `):` ` ` `# Inserting every sum` ` ` `s.add(i ` `+` `j)` ` ` ` ` `# Returning distinct sums` ` ` `return` `len` `(s)` `# Driver code` `N ` `=` `3` `print` `(findDistinctSums(N))` ` ` `# This code is contributed by divyamohan123` |

## C#

`// C# implementation to count` `// of distinct pair sum between` `// two Array with values 1 to N` `using` `System;` `using` `System.Collections.Generic;` `class` `GFG{` `// Function to find the distinct sums` `static` `int` `findDistinctSums(` `int` `n)` `{` ` ` ` ` `// Set to store distinct sums` ` ` `HashSet<` `int` `> s = ` `new` `HashSet<` `int` `>();` ` ` `for` `(` `int` `i = 1; i <= n; i++)` ` ` `{` ` ` `for` `(` `int` `j = i; j <= n; j++)` ` ` `{` ` ` ` ` `// Inserting every sum` ` ` `s.Add(i + j);` ` ` `}` ` ` `}` ` ` ` ` `// Returning distinct sums` ` ` `return` `s.Count;` `}` `// Driver code` `public` `static` `void` `Main(String[] args)` `{` ` ` `int` `N = 3;` ` ` `Console.Write(findDistinctSums(N));` `}` `}` `// This code is contributed by gauravrajput1` |

## Javascript

`<script>` `// Javascript implementation to count` `// of distinct pair sum between` `// two Array with values 1 to N` `// Function to find the distinct sums` `function` `findDistinctSums(n)` `{` ` ` `// Set to store distinct sums` ` ` `s = ` `new` `Set();` ` ` `for` `(` `var` `i = 1; i <= n; i++) {` ` ` `for` `(` `var` `j = i; j <= n; j++) {` ` ` `// Inserting every sum` ` ` `s.add(i + j);` ` ` `}` ` ` `}` ` ` `// returning distinct sums` ` ` `return` `s.size;` `}` `// Driver code` `var` `N = 3;` `document.write( findDistinctSums(N));` `</script>` |

**Output:**

5

**Efficient approach:** To optimize the above method:

- Observe that the series formed for the count of distinct sums in {1, 2, 3, .., N} and {1, 2, 3, .., N} is given as
**1, 3, 5, 7, …**

- Therefore Nth term of the above series =
**2 * N – 1** - Hence the count of distinct pair sum can be calculated as
**2 * N – 1**

Below is the implementation of above approach:

## C++

`// C++ implementation to find count` `// of distinct pair sum between` `// two 1 to N value Arrays` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to find the distinct sums` `int` `findDistinctSums(` `int` `N)` `{` ` ` `return` `(2 * N - 1);` `}` `// Driver code` `int` `main()` `{` ` ` `int` `N = 3;` ` ` `cout << findDistinctSums(N);` ` ` `return` `0;` `}` |

## Java

`// Java implementation to find count` `// of distinct pair sum between` `// two 1 to N value Arrays` `import` `java.util.*;` `class` `GFG{` `// Function to find the distinct sums` `static` `int` `findDistinctSums(` `int` `N)` `{` ` ` `return` `(` `2` `* N - ` `1` `);` `}` `// Driver code` `public` `static` `void` `main(String[] args)` `{` ` ` `int` `N = ` `3` `;` ` ` `System.out.print(findDistinctSums(N));` `}` `}` `// This code is contributed by shivanisinghss2110` |

## Python3

`# Python3 implementation to find count` `# of distinct pair sum between` `# two 1 to N value Arrays` `# Function to find the distinct sums` `def` `findDistinctSums(N):` ` ` `return` `(` `2` `*` `N ` `-` `1` `)` `# Driver code` `N ` `=` `3` `print` `(findDistinctSums(N))` `# This code is contributed by divyamohan123` |

## C#

`// C# implementation to find count` `// of distinct pair sum between` `// two 1 to N value Arrays` `using` `System;` `class` `GFG{` `// Function to find the distinct sums` `static` `int` `findDistinctSums(` `int` `N)` `{` ` ` `return` `(2 * N - 1);` `}` `// Driver code` `public` `static` `void` `Main()` `{` ` ` `int` `N = 3;` ` ` `Console.Write(findDistinctSums(N));` `}` `}` `// This code is contributed by Code_Mech` |

## Javascript

`<script>` ` ` `// Javascript implementation to find count` ` ` `// of distinct pair sum between` ` ` `// two 1 to N value Arrays` ` ` ` ` `// Function to find the distinct sums` ` ` `function` `findDistinctSums(N)` ` ` `{` ` ` `return` `(2 * N - 1);` ` ` `}` ` ` ` ` `let N = 3;` ` ` ` ` `document.write(findDistinctSums(N));` `</script>` |

**Output:**

5

**Time Complexity: **O(1)**Auxiliary Space Complexity: **O(1)