Saturday, January 11, 2025
Google search engine
HomeData Modelling & AICount Pronic numbers from a given range

Count Pronic numbers from a given range

Given two integers A and B, the task is to count the number of pronic numbers that are present in the range [A, B].

Examples:

Input: A = 3, B = 20
Output: 3
Explanation: The pronic numbers from the range [3, 20] are 6, 12, 20

Input: A = 5000, B = 990000000
Output: 31393

Naive Approach: Follow the given steps to solve the problem:

  1. Initialize the count of pronic numbers to 0.
  2. For every number in the range [A, B], check whether it is a pronic integer or not
  3. If found to be true, increment the count.
  4. Finally, print the count

Below is the implementation of the above approach:

C++14




// C++ program for
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if x
// is a Pronic Number or not
bool checkPronic(int x)
{
 
    for (int i = 0; i <= (int)(sqrt(x));
         i++) {
 
        // Check for Pronic Number by
        // multiplying consecutive
        // numbers
        if (x == i * (i + 1)) {
            return true;
        }
    }
    return false;
}
 
// Function to count pronic
// numbers in the range [A, B]
void countPronic(int A, int B)
{
    // Initialise count
    int count = 0;
 
    // Iterate from A to B
    for (int i = A; i <= B; i++) {
 
        // If i is pronic
        if (checkPronic(i)) {
 
            // Increment count
            count++;
        }
    }
 
    // Print count
    cout << count;
}
 
// Driver Code
int main()
{
    int A = 3, B = 20;
 
    // Function call to count pronic
    // numbers in the range [A, B]
    countPronic(A, B);
 
    return 0;
}


Java




// Java program to implement
// the above approach
import java.util.*;
 
class GFG{
 
// Function to check if x
// is a Pronic Number or not
static boolean checkPronic(int x)
{
 
    for (int i = 0; i <= (int)(Math.sqrt(x));
         i++) {
 
        // Check for Pronic Number by
        // multiplying consecutive
        // numbers
        if ((x == i * (i + 1)) != false) {
            return true;
        }
    }
    return false;
}
 
// Function to count pronic
// numbers in the range [A, B]
static void countPronic(int A, int B)
{
    // Initialise count
    int count = 0;
 
    // Iterate from A to B
    for (int i = A; i <= B; i++) {
 
        // If i is pronic
        if (checkPronic(i) != false) {
 
            // Increment count
            count++;
        }
    }
 
    // Print count
    System.out.print(count);
}
 
// Driver Code
public static void main(String args[])
{
    int A = 3, B = 20;
 
    // Function call to count pronic
    // numbers in the range [A, B]
    countPronic(A, B);
}
}
 
// This code is contributed by sanjoy_62.


Python3




# Python3 program for the above approach
import math
 
# Function to check if x
# is a Pronic Number or not
def checkPronic(x) :
    for i in range(int(math.sqrt(x)) + 1):
 
        # Check for Pronic Number by
        # multiplying consecutive
        # numbers
        if (x == i * (i + 1)) :
            return True
    return False
   
# Function to count pronic
# numbers in the range [A, B]
def countPronic(A, B) :
     
    # Initialise count
    count = 0
 
    # Iterate from A to B
    for i in range(A, B + 1):
 
        # If i is pronic
        if (checkPronic(i) != 0) :
 
            # Increment count
            count += 1
         
    # Print count
    print(count)
 
# Driver Code
A = 3
B = 20
 
# Function call to count pronic
# numbers in the range [A, B]
countPronic(A, B)
 
# This code is contributed by susmitakundugoaldanga.


C#




// C# program for the above approach
using System;
public class GFG
{
 
// Function to check if x
// is a Pronic Number or not
static bool checkPronic(int x)
{
 
    for (int i = 0; i <= (int)(Math.Sqrt(x));
         i++)
    {
 
        // Check for Pronic Number by
        // multiplying consecutive
        // numbers
        if ((x == i * (i + 1)) != false)
        {
            return true;
        }
    }
    return false;
}
 
// Function to count pronic
// numbers in the range [A, B]
static void countPronic(int A, int B)
{
   
    // Initialise count
    int count = 0;
 
    // Iterate from A to B
    for (int i = A; i <= B; i++)
    {
 
        // If i is pronic
        if (checkPronic(i) != false)
        {
 
            // Increment count
            count++;
        }
    }
 
    // Print count
    Console.Write(count);
}
 
 
// Driver Code
public static void Main(String[] args)
{
    int A = 3, B = 20;
 
    // Function call to count pronic
    // numbers in the range [A, B]
    countPronic(A, B);
}
}
 
// This code is contributed by code_hunt.


Javascript




<script>
 
// Javascript program for
// the above approach
 
// Function to check if x
// is a Pronic Number or not
function checkPronic(x)
{
 
    for (let i = 0; i <= parseInt(Math.sqrt(x));
         i++) {
 
        // Check for Pronic Number by
        // multiplying consecutive
        // numbers
        if (x == i * (i + 1)) {
            return true;
        }
    }
    return false;
}
 
// Function to count pronic
// numbers in the range [A, B]
function countPronic(A, B)
{
    // Initialise count
    let count = 0;
 
    // Iterate from A to B
    for (let i = A; i <= B; i++) {
 
        // If i is pronic
        if (checkPronic(i)) {
 
            // Increment count
            count++;
        }
    }
 
    // Print count
    document.write(count);
}
 
// Driver Code
let A = 3, B = 20;
 
// Function call to count pronic
// numbers in the range [A, B]
countPronic(A, B);
 
</script>


 
 

Output: 

3

 

Time Complexity: O((B – A) * ?(B – A))
Auxiliary Space: O(1)

Efficient Approach: Follow the below steps to solve the problem:

  1. Define a function pronic(N) to find the count of pronic integers which are ? N.
  2. Calculate the square root of N, say X.
  3. If product of X and X – 1 is less than or equal to N, return N.
  4. Otherwise, return N – 1.
  5. Print pronic(B) – pronic(A – 1) to get the count of pronic integers in the range [A, B]

Below is the implementation of the above approach:

C++14




// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count pronic
// numbers in the range [A, B]
int pronic(int num)
{
    // Check upto sqrt N
    int N = (int)sqrt(num);
 
    // If product of consecutive
    // numbers are less than equal to num
    if (N * (N + 1) <= num) {
        return N;
    }
 
    // Return N - 1
    return N - 1;
}
 
// Function to count pronic
// numbers in the range [A, B]
int countPronic(int A, int B)
{
    // Subtract the count of pronic numbers
    // which are <= (A - 1) from the count
    // f pronic numbers which are <= B
    return pronic(B) - pronic(A - 1);
}
 
// Driver Code
int main()
{
    int A = 3;
    int B = 20;
 
    // Function call to count pronic
    // numbers in the range [A, B]
    cout << countPronic(A, B);
 
    return 0;
}


Java




// Java program for the above approach
import java.util.*;
class GFG
{
 
// Function to count pronic
// numbers in the range [A, B]
static int pronic(int num)
{
   
    // Check upto sqrt N
    int N = (int)Math.sqrt(num);
 
    // If product of consecutive
    // numbers are less than equal to num
    if (N * (N + 1) <= num)
    {
        return N;
    }
 
    // Return N - 1
    return N - 1;
}
 
// Function to count pronic
// numbers in the range [A, B]
static int countPronic(int A, int B)
{
   
    // Subtract the count of pronic numbers
    // which are <= (A - 1) from the count
    // f pronic numbers which are <= B
    return pronic(B) - pronic(A - 1);
}
 
// Driver Code
public static void main(String[] args)
{
    int A = 3;
    int B = 20;
 
    // Function call to count pronic
    // numbers in the range [A, B]
    System.out.print(countPronic(A, B));
 
}
}
 
// This code is contributed by shikhasingrajput


Python3




# Python3 program for the above approach
 
# Function to count pronic
# numbers in the range [A, B]
def pronic(num) :
 
    # Check upto sqrt N
    N = int(num ** (1/2));
 
    # If product of consecutive
    # numbers are less than equal to num
    if (N * (N + 1) <= num) :
        return N;
 
    # Return N - 1
    return N - 1;
 
# Function to count pronic
# numbers in the range [A, B]
def countPronic(A, B) :
     
    # Subtract the count of pronic numbers
    # which are <= (A - 1) from the count
    # f pronic numbers which are <= B
    return pronic(B) - pronic(A - 1);
 
# Driver Code
if __name__ == "__main__" :
 
    A = 3;
    B = 20;
 
    # Function call to count pronic
    # numbers in the range [A, B]
    print(countPronic(A, B));
 
    # This code is contributed by AnkThon


C#




// C# program for the above approach
using System;
public class GFG
{
 
// Function to count pronic
// numbers in the range [A, B]
static int pronic(int num)
{
   
    // Check upto sqrt N
    int N = (int)Math.Sqrt(num);
 
    // If product of consecutive
    // numbers are less than equal to num
    if (N * (N + 1) <= num)
    {
        return N;
    }
 
    // Return N - 1
    return N - 1;
}
 
// Function to count pronic
// numbers in the range [A, B]
static int countPronic(int A, int B)
{
   
    // Subtract the count of pronic numbers
    // which are <= (A - 1) from the count
    // f pronic numbers which are <= B
    return pronic(B) - pronic(A - 1);
}
 
// Driver Code
public static void Main(String[] args)
{
    int A = 3;
    int B = 20;
 
    // Function call to count pronic
    // numbers in the range [A, B]
    Console.Write(countPronic(A, B));
}
}
 
// This code is contributed by 29AjayKumar


Javascript




<script>
 
// Javascript program for the above approach
 
// Function to count pronic
// numbers in the range [A, B]
function pronic(num)
{
 
    // Check upto sqrt N
    var N = parseInt(Math.sqrt(num));
 
    // If product of consecutive
    // numbers are less than equal to num
    if (N * (N + 1) <= num) {
        return N;
    }
 
    // Return N - 1
    return N - 1;
}
 
// Function to count pronic
// numbers in the range [A, B]
function countPronic(A, B)
{
 
    // Subtract the count of pronic numbers
    // which are <= (A - 1) from the count
    // f pronic numbers which are <= B
    return pronic(B) - pronic(A - 1);
}
 
// Driver Code
var A = 3;
var B = 20;
 
// Function call to count pronic
// numbers in the range [A, B]
document.write(countPronic(A, B));
 
// This code is contributed by noob2000.
</script>


 
 

Output: 

3

 

Time Complexity: O(log2(B))
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!

RELATED ARTICLES

Most Popular

Recent Comments