Count of pairs with sum N from first N natural numbers

0 0 5 minutes read

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 Code
int main()
{
    int n = 8;
    cout << numberOfPairs(n);
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
 
class GFG{
     
// Function to calculate the value of count
public 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 code
public 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 approach
def 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 code
if __name__=='__main__':
   
  n = 8
  print(numberOfPairs(n))
     
# This code is contributed by virusbuddah_

C#

// C# program for the above approach
using System;
class GFG{
      
// Function to calculate the value of count
public 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 code
public 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 approach
function 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 code
let n = 8;
 
document.write(numberOfPairs(n));
     
// This code is contributed by divyesh072019
     
</script>

Output

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 – 1

N = 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 pairs
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 Code
int 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 N
import java.io.*;
 
class GFG{
     
// Function to calculate the value of count
public 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 code
public 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 count
def numberOfPairs(n):
 
    # If n is even
    if (n % 2 == 0):
 
        # Count of pairs
        return n // 2 - 1;
 
    # Otherwise
    else:
        return n // 2;
 
# Driver code
n = 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 N
using System;
class GFG{
      
// Function to calculate the value of count
public 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 code
public 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 pairs
function numberOfPairs(n)
{
     
    // If n is even
    if (n % 2 == 0)
 
        // Count of pairs
        return (n / 2 - 1);
 
    // Otherwise
    else
        return (n / 2);
}
 
// Driver code
let n = 8;
 
document.write(numberOfPairs(n));
 
// This code is contributed by rameshtravel07
 
</script>

Output

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 zambiatek!