Given an integer N, the task is to count the number of pairs among the first N natural numbers, with sum equal to N.
Examples:
Input: N = 8
Output: 3
Explanation:
All possible pairs with sum 8 are { (1, 7), (2, 6), (3, 5)}Input: N = 9
Output: 4
Naive Approach:
The simplest approach to solve the problem is to use Two Pointers. Follow the steps below to solve the problem:
- Set i = 0 and j = N – 1 initially.
- Iterate until i >= j, and for every pair of i, j, check if their sum is equal to N or not. If so, increase the count of pairs.
- Move to the next pair by increasing and decreasing i and j by 1 respectively.
- Finally, print the count of pairs obtained.
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include <iostream>using namespace std;Â
int numberOfPairs(int n){Â
    // Stores the count of    // pairs    int count = 0;    // Set the two pointers    int i = 1, j = n - 1;Â
    while (i < j) {Â
        // Check if the sum of        // pairs is equal to N        if (i + j == n) {            // Increase the count            // of pairs            count++;        }Â
        // Move to the next pair        i++;        j--;    }Â
    return count;}Â
// Driver Codeint main(){Â Â Â Â int n = 8;Â Â Â Â cout << numberOfPairs(n);Â Â Â Â return 0;} |
Java
// Java program for the above approachimport java.io.*;Â
class GFG{Â Â Â Â Â // Function to calculate the value of countpublic static int numberOfPairs(int n){Â
    // Stores the count of pairs    int count = 0;Â
    // Set the two pointers    int i = 1, j = n - 1;Â
    while (i < j)    {                 // Check if the sum of        // pairs is equal to N        if (i + j == n)        {                         // Increase the count            // of pairs            count++;        }Â
        // Move to the next pair        i++;        j--;    }    return count;}Â
// Driver codepublic static void main (String[] args){Â Â Â Â int n = 8;Â Â Â Â Â Â Â Â Â System.out.println(numberOfPairs(n));}}Â
// This code is contributed by piyush3010 |
Python3
# Python3 program for the# above approachdef numberOfPairs(n):     # Stores the count  # of pairs  count = 0     # Set the two pointers  i = 1  j = n - 1Â
  while(i < j):         # Check if the sum    # of pirs is equal to n    if (i + j) == n:             # Increase the count of pairs      count += 1             # Move to the next pair      i += 1      j -= 1         return countÂ
# Driver codeif __name__=='__main__':Â Â Â Â Â n = 8Â Â print(numberOfPairs(n))Â Â Â Â Â # This code is contributed by virusbuddah_ |
C#
// C# program for the above approachusing System;class GFG{      // Function to calculate the value of countpublic static int numberOfPairs(int n){      // Stores the count of pairs    int count = 0;      // Set the two pointers    int i = 1, j = n - 1;      while (i < j)    {                  // Check if the sum of        // pairs is equal to N        if (i + j == n)        {                          // Increase the count            // of pairs            count++;        }          // Move to the next pair        i++;        j--;    }    return count;}  // Driver codepublic static void Main (string[] args){    int n = 8;          Console.Write(numberOfPairs(n));}}  // This code is contributed by rock_cool |
Javascript
<script>Â
// Javascript program to implement// the above approachfunction numberOfPairs(n){         // Stores the count of    // pairs    let count = 0;         // Set the two pointers    let i = 1, j = n - 1;Â
    while (i < j)     {                 // Check if the sum of        // pairs is equal to N        if (i + j == n)        {                         // Increase the count            // of pairs            count++;        }Â
        // Move to the next pair        i++;        j--;    }    return count;}Â
// Driver codelet n = 8;Â
document.write(numberOfPairs(n));Â Â Â Â Â // This code is contributed by divyesh072019Â Â Â Â Â </script> |
Output
3
Time Complexity: O(N)Â
Auxiliary Space: O(1)
Efficient Approach:
To optimize the above approach, we just need to observe if N is even or odd. If N is even, the count of possible pairs is N/2 – 1. Otherwise, it is  N/2.Â
Illustration:
N = 8
All possible pairs are (1, 7), (2, 6) and (3, 5)
Hence, count of possible pairs = 3 = 8/2 – 1N = 9
All possible pairs are (1, 8), (2, 7), (3, 6) and (4, 5)
Hence, count of possible pairs = 4 = 9/2
Below is the implementation of the above approach:Â
C++
// C++ program to count the number// of pairs among the first N// natural numbers with sum N#include <iostream>using namespace std;Â
// Function to return the// count of pairsint numberOfPairs(int n){    // If n is even    if (n % 2 == 0)Â
        // Count of pairs        return n / 2 - 1;Â
    // Otherwise    else        return n / 2;}Â
// Driver Codeint main(){Â Â Â Â int n = 8;Â Â Â Â cout << numberOfPairs(n);Â
    return 0;} |
Java
// Java program to count the number// of pairs among the first N// natural numbers with sum Nimport java.io.*;Â
class GFG{Â Â Â Â Â // Function to calculate the value of countpublic static int numberOfPairs(int n){Â
    // If n is even    if (n % 2 == 0)             // Count of pairs        return n / 2 - 1;Â
    // Otherwise    else        return n / 2;}Â
// Driver codepublic static void main (String[] args){Â Â Â Â int n = 8;Â Â Â Â Â Â Â Â Â System.out.println(numberOfPairs(n));}}Â
// This code is contributed by piyush3010 |
Python3
# Python3 program to count the number# of pairs among the first N# natural numbers with sum NÂ
# Function to calculate the value of countdef numberOfPairs(n):Â
    # If n is even    if (n % 2 == 0):Â
        # Count of pairs        return n // 2 - 1;Â
    # Otherwise    else:        return n // 2;Â
# Driver coden = 8;Â
print(numberOfPairs(n));Â
# This code is contributed by Rajput-Ji |
C#
// C# program to count the number// of pairs among the first N// natural numbers with sum Nusing System;class GFG{      // Function to calculate the value of countpublic static int numberOfPairs(int n){      // If n is even    if (n % 2 == 0)              // Count of pairs        return n / 2 - 1;      // Otherwise    else        return n / 2;}  // Driver codepublic static void Main (string[] args){    int n = 8;          Console.Write(numberOfPairs(n));}}  // This code is contributed by Ritik Bansal |
Javascript
<script>Â
// Javascript program to count the number// of pairs among the first N// natural numbers with sum NÂ
// Function to return the// count of pairsfunction numberOfPairs(n){         // If n is even    if (n % 2 == 0)Â
        // Count of pairs        return (n / 2 - 1);Â
    // Otherwise    else        return (n / 2);}Â
// Driver codelet n = 8;Â
document.write(numberOfPairs(n));Â
// This code is contributed by rameshtravel07Â
</script> |
Output
3
Time Complexity: O(1)Â
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
