Count of Perfect Numbers in given range for Q queries
Given an array arr[] consisting of N pairs, where each pair represents a query of the form {L, R}, the task is to find the count of perfect numbers in the given range for each query.
Examples:
Input: arr[][] = {{1, 10}, {10, 20}, {20, 30}}
Output: 1 1 1
Explanation:
- Query(1, 10): Perfect numbers in the range is only 6.
- Query(10, 20): There are no perfect numbers in the range.
- Query(20, 30): The perfect number in the range is only 28.
Input: arr[][] = {{1, 1000}, {1000, 2000}, {2000, 3000}
Output: 3 0 0
Explanation:
- Query(1, 1000): Perfect numbers in the range are 6, 28, and 496.
- Query(1000, 2000): There are no perfect numbers in the range.
- Query(2000, 3000): There are no perfect numbers in the range.
Naive Approach: The simplest approach is, iterate over the range in each query and check if a number is a perfect number or not, and then print the count of perfect numbers in the range for the respective query.
Time Complexity: O(N*M*?M)), where M is the largest size of a range.
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized by prestoring the count of perfect Numbers from 1 to every other number using the prefix sum array technique, which results in constant time calculation of each query. Follow the steps below to solve the problem:
- Find the maximum value of the right boundary of a range by traversing the array arr[] and store it in a variable, say MAX.
- Initialize an array, say prefix[] of size MAX+1 with the value of each element as 0, where the prefix[i] stores the count of perfect numbers up to i.
- Iterate over the range [2, MAX] using the variable i and do the following:
- Update prefix[i] to prefix[i-1] and then check if current integer i is a perfect number then increase prefix[i] by 1.
- Traverse the array arr[] and in each iteration print the count of perfect numbers in the current range, [L, R] as prefix[R] – prefix[L-1].
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; const int MAX = 100005; // Function to check whether a number // is perfect Number bool isPerfect( long long int N) { // Stores sum of divisors long long int sum = 1; // Iterate over the range[2, sqrt(N)] for ( long long int i = 2; i * i <= N; i++) { if (N % i == 0) { if (i * i != N) sum = sum + i + N / i; else sum = sum + i; } } // If sum of divisors is equal to // N, then N is a perfect number if (sum == N && N != 1) return true ; return false ; } // Function to find count of perfect // numbers in a given range void Query( int arr[][2], int N) { // Stores the count of perfect Numbers // upto a every number less than MAX int prefix[MAX + 1] = { 0 }; // Iterate over the range [1, MAX] for ( int i = 2; i <= MAX; i++) { prefix[i] = prefix[i - 1] + isPerfect(i); } // Traverse the array arr[] for ( int i = 0; i < N; i++) { // Print the count of perfect numbers // in the range [arr[i][0], arr[i][1]] cout << prefix[arr[i][1]] - prefix[arr[i][0] - 1] << " " ; } } // Driver Code int main() { int arr[][2] = { { 1, 1000 }, { 1000, 2000 }, { 2000, 3000 } }; int N = sizeof (arr) / sizeof (arr[0]); Query(arr, N); } |
Java
// C++ program for the above approach import java.util.*; public class MyClass { static int MAX = 100005 ; // Function to check whether a number // is perfect Number static int isPerfect( long N) { // Stores sum of divisors long sum = 1 ; // Iterate over the range[2, sqrt(N)] for ( long i = 2 ; i * i <= N; i++) { if (N % i == 0 ) { if (i * i != N) sum = sum + i + N / i; else sum = sum + i; } } // If sum of divisors is equal to // N, then N is a perfect number if (sum == N && N != 1 ) return 1 ; return 0 ; } // Function to find count of perfect // numbers in a given range static void Query( int arr[][], int N) { // Stores the count of perfect Numbers // upto a every number less than MAX int []prefix = new int [MAX + 1 ]; Arrays.fill(prefix, 0 ); // Iterate over the range [1, MAX] for ( int i = 2 ; i <= MAX; i++) { prefix[i] = prefix[i - 1 ] + isPerfect(i); } // Traverse the array arr[] for ( int i = 0 ; i < N; i++) { // Print the count of perfect numbers // in the range [arr[i][0], arr[i][1]] System.out.print( prefix[arr[i][ 1 ]] - prefix[arr[i][ 0 ] - 1 ]+ " " ); } } // Driver Code public static void main(String args[]) { int [][]arr = { { 1 , 1000 }, { 1000 , 2000 }, { 2000 , 3000 } }; int N = arr.length; Query(arr, N); } } // This code is contributed by SoumikMondal |
Python3
# python 3 program for the above approach MAX = 100005 from math import sqrt # Function to check whether a number # is perfect Number def isPerfect(N): # Stores sum of divisors sum = 1 # Iterate over the range[2, sqrt(N)] for i in range ( 2 , int (sqrt(N)) + 1 , 1 ): if (N % i = = 0 ): if (i * i ! = N): sum = sum + i + N / / i else : sum = sum + i # If sum of divisors is equal to # N, then N is a perfect number if ( sum = = N and N ! = 1 ): return True return False # Function to find count of perfect # numbers in a given range def Query(arr, N): # Stores the count of perfect Numbers # upto a every number less than MAX prefix = [ 0 for i in range ( MAX + 1 )] # Iterate over the range [1, MAX] for i in range ( 2 , MAX + 1 , 1 ): prefix[i] = prefix[i - 1 ] + isPerfect(i) # Traverse the array arr[] for i in range (N): # Print the count of perfect numbers # in the range [arr[i][0], arr[i][1]] print (prefix[arr[i][ 1 ]] - prefix[arr[i][ 0 ] - 1 ],end = " " ) # Driver Code if __name__ = = '__main__' : arr = [[ 1 , 1000 ],[ 1000 , 2000 ],[ 2000 , 3000 ]] N = len (arr) Query(arr, N) # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# program for the above approach using System; public class MyClass { static int MAX = 100005; // Function to check whether a number // is perfect Number static int isPerfect( long N) { // Stores sum of divisors long sum = 1; // Iterate over the range[2, sqrt(N)] for ( long i = 2; i * i <= N; i++) { if (N % i == 0) { if (i * i != N) sum = sum + i + N / i; else sum = sum + i; } } // If sum of divisors is equal to // N, then N is a perfect number if (sum == N && N != 1) return 1; return 0; } // Function to find count of perfect // numbers in a given range static void Query( int [, ] arr, int N) { // Stores the count of perfect Numbers // upto a every number less than MAX int [] prefix = new int [MAX + 1]; // Arrays.fill(prefix,0); // Iterate over the range [1, MAX] for ( int i = 2; i <= MAX; i++) { prefix[i] = prefix[i - 1] + isPerfect(i); } // Traverse the array arr[] for ( int i = 0; i < N; i++) { // Print the count of perfect numbers // in the range [arr[i][0], arr[i][1]] Console.Write(prefix[arr[i, 1]] - prefix[arr[i, 0] - 1] + " " ); } } // Driver Code public static void Main() { int [, ] arr = { { 1, 1000 }, { 1000, 2000 }, { 2000, 3000 } }; int N = arr.GetLength(0); Query(arr, N); } } // This code is contributed by ukasp. |
Javascript
<script> // JavaScript program for the above approach const MAX = 100005; // Function to check whether a number // is perfect Number function isPerfect(N) { // Stores sum of divisors let sum = 1; // Iterate over the range[2, sqrt(N)] for (let i = 2; i * i <= N; i++) { if (N % i == 0) { if (i * i != N) sum = sum + i + Math.floor(N / i); else sum = sum + i; } } // If sum of divisors is equal to // N, then N is a perfect number if (sum == N && N != 1) return true ; return false ; } // Function to find count of perfect // numbers in a given range function Query(arr, N) { // Stores the count of perfect Numbers // upto a every number less than MAX let prefix = new Array(MAX + 1).fill(0); // Iterate over the range [1, MAX] for (let i = 2; i <= MAX; i++) { prefix[i] = prefix[i - 1] + isPerfect(i); } // Traverse the array arr[] for (let i = 0; i < N; i++) { // Print the count of perfect numbers // in the range [arr[i][0], arr[i][1]] document.write(prefix[arr[i][1]] - prefix[arr[i][0] - 1] + " " ); } } // Driver Code let arr = [[1, 1000], [1000, 2000], [2000, 3000]]; let N = arr.length; Query(arr, N); // This code is contributed by Potta Lokesh </script> |
3 0 0
Time Complexity: O(M*?M+ N), where M is the largest right boundary.
Auxiliary Space: O(M)