Given two arrays L[] and R[] of sizes Q, the task is to find the number of composite magic numbers i.e numbers which are both composite numbers as well as Magic numbers from the range [L[i], R[i]] ( 0 ? i < Q).
Examples:
Input: Q = 1, L[] = {10}, R[] = {100}
Output: 8
Explanation: Numbers in the range [L[0], R[0]] which are both composite as well as Magic numbers are {10, 28, 46, 55, 64, 82, 91, 100}.Input: Q = 1, L[] = {1200}, R[] = {1300}
Output: 9
Explanation: Numbers in the range [L[0], R[0]] which are both composite as well as Magic numbers are {1207, 1216, 1225, 1234, 1243, 1252, 1261, 1270, 1288}.
Naive Approach: The simplest approach to solve the problem is to traverse all the numbers in the range [L[i], R[i]] (0 ? i < Q) and for every number, check if it is composite as well as a magic number or not.
Time Complexity: O(Q * N3/2)
Auxiliary Space: O(N)
Efficient Approach: To optimize the above approach, precompute and store the counts of Composite Magic Numbers in an array over a certain range. This optimizes the computational complexities of each query to O(1). Follow the steps below to solve the problem:
- Initialize an integer array dp[] such that dp[i] stores the count of Composite Magic Numbers up to i.
- Traverse the range [1, 106] and for every number in the range, check if it is a Composite Magic Number or not. If found to be true, update dp[i] with dp[i – 1] + 1 . Otherwise, update dp[i] with dp[i – 1]
- Traverse the arrays L[] and R[] simultaneously and print dp[R[i]] – dp[L[i] – 1] as the required answer.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <iostream>using namespace std;// Check if a number is magic// number or notbool isMagic(int num){ return (num % 9 == 1);}// Check number is composite// number or notbool isComposite(int n){ // Corner cases if (n <= 1) return false; if (n <= 3) return false; // Check if the number is // a multiple of 2 or 3 if (n % 2 == 0 || n % 3 == 0) return true; // Check for multiples of remaining primes for (int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return true; return false;}// Function to find Composite Magic// Numbers in given rangesvoid find(int L[], int R[], int q){ // dp[i]: Stores the count of // composite Magic numbers up to i int dp[1000005]; dp[0] = 0; dp[1] = 0; // Traverse in the range [1, 1e5) for (int i = 1; i < 1000005; i++) { // Check if number is Composite number // as well as a Magic number or not if (isComposite(i) && isMagic(i)) { dp[i] = dp[i - 1] + 1; } else dp[i] = dp[i - 1]; } // Print results for each query for (int i = 0; i < q; i++) cout << dp[R[i]] - dp[L[i] - 1] << endl;}// Driver Codeint main(){ int L[] = { 10, 3 }; int R[] = { 100, 2279 }; int Q = 2; find(L, R, Q); return 0;} |
Java
// Java program to implement// the above approachclass GFG{ // Check if a number is magic // number or not static boolean isMagic(int num) { return (num % 9 == 1); } // Check number is composite // number or not static boolean isComposite(int n) { // Corner cases if (n <= 1) return false; if (n <= 3) return false; // Check if the number is // a multiple of 2 or 3 if (n % 2 == 0 || n % 3 == 0) return true; // Check for multiples of remaining primes for (int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return true; return false; } // Function to find Composite Magic // Numbers in given ranges static void find(int L[], int R[], int q) { // dp[i]: Stores the count of // composite Magic numbers up to i int dp[] = new int[1000005]; dp[0] = 0; dp[1] = 0; // Traverse in the range [1, 1e5) for (int i = 1; i < 1000005; i++) { // Check if number is Composite number // as well as a Magic number or not if (isComposite(i) && isMagic(i) == true) { dp[i] = dp[i - 1] + 1; } else dp[i] = dp[i - 1]; } // Print results for each query for (int i = 0; i < q; i++) System.out.println(dp[R[i]] - dp[L[i] - 1]); } // Driver Code public static void main (String[] args) { int L[] = { 10, 3 }; int R[] = { 100, 2279 }; int Q = 2; find(L, R, Q); }}// This code is contributed by AnkThon |
Python3
# Python3 program to implement# the above approach# Check if a number is magic# number or notdef isMagic(num): return (num % 9 == 1)# Check number is composite# number or notdef isComposite(n): # Corner cases if (n <= 1): return False if (n <= 3): return False # Check if the number is # a multiple of 2 or 3 if (n % 2 == 0 or n % 3 == 0): return True # Check for multiples of remaining primes for i in range(5, n + 1, 6): if i * i > n + 1: break if (n % i == 0 or n % (i + 2) == 0): return True return False# Function to find Composite Magic# Numbers in given rangesdef find(L, R, q): # dp[i]: Stores the count of # composite Magic numbers up to i dp = [0] * 1000005 dp[0] = 0 dp[1] = 0 # Traverse in the range [1, 1e5) for i in range(1, 1000005): # Check if number is Composite number # as well as a Magic number or not if (isComposite(i) and isMagic(i)): dp[i] = dp[i - 1] + 1 else: dp[i] = dp[i - 1] # Print results for each query for i in range(q): print(dp[R[i]] - dp[L[i] - 1])# Driver Codeif __name__ == '__main__': L = [ 10, 3 ] R = [ 100, 2279 ] Q = 2 find(L, R, Q)# This code is contributed by mohit kumar 29 |
C#
// C# program to implement// the above approach using System;class GFG{ // Check if a number is magic// number or notstatic bool isMagic(int num){ return (num % 9 == 1);} // Check number is composite// number or notstatic bool isComposite(int n){ // Corner cases if (n <= 1) return false; if (n <= 3) return false; // Check if the number is // a multiple of 2 or 3 if (n % 2 == 0 || n % 3 == 0) return true; // Check for multiples of remaining primes for(int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return true; return false;} // Function to find Composite Magic// Numbers in given rangesstatic void find(int[] L, int[] R, int q){ // dp[i]: Stores the count of // composite Magic numbers up to i int[] dp = new int[1000005]; dp[0] = 0; dp[1] = 0; // Traverse in the range [1, 1e5) for(int i = 1; i < 1000005; i++) { // Check if number is Composite number // as well as a Magic number or not if (isComposite(i) && isMagic(i) == true) { dp[i] = dp[i - 1] + 1; } else dp[i] = dp[i - 1]; } // Print results for each query for(int i = 0; i < q; i++) Console.WriteLine(dp[R[i]] - dp[L[i] - 1]);} // Driver Codepublic static void Main (){ int[] L = { 10, 3 }; int[] R = { 100, 2279 }; int Q = 2; find(L, R, Q);}}// This code is contributed by susmitakundugoaldanga |
Javascript
<script>// JavaScript program to implement// the above approach // Check if a number is magic // number or not function isMagic(num) { return (num % 9 == 1); } // Check number is composite // number or not function isComposite(n) { // Corner cases if (n <= 1) return false; if (n <= 3) return false; // Check if the number is // a multiple of 2 or 3 if (n % 2 == 0 || n % 3 == 0) return true; // Check for multiples of remaining primes for (let i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return true; return false; } // Function to find Composite Magic // Numbers in given ranges function find(L, R, q) { // dp[i]: Stores the count of // composite Magic numbers up to i let dp = []; dp[0] = 0; dp[1] = 0; // Traverse in the range [1, 1e5) for (let i = 1; i < 1000005; i++) { // Check if number is Composite number // as well as a Magic number or not if (isComposite(i) && isMagic(i) == true) { dp[i] = dp[i - 1] + 1; } else dp[i] = dp[i - 1]; } // Print results for each query for (let i = 0; i < q; i++) document.write(dp[R[i]] - dp[L[i] - 1] + "<br/>"); } // Driver code let L = [ 10, 3 ]; let R = [100, 2279 ]; let Q = 2; find(L, R, Q);</script> |
Output:
8 198
Time Complexity: O(N3/2)
Auxiliary Space: O(N)
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!
