Given two positive integers L and R, the task is to count the elements from the range [L, R] whose prime factors are only 2 and 3.
Examples:
Input: L = 1, R = 10
Output: 6
Explanation:
2 = 2
3 = 3
4 = 2 * 2
6 = 2 * 3
8 = 2 * 2 * 2
9 = 3 * 3
Input: L = 100, R = 200
Output: 5
For a simpler approach, refer to Count numbers from range whose prime factors are only 2 and 3.
Approach:
To solve the problem in an optimized way, follow the steps given below:
- Store all the powers of 2 which are less than or equal to R in an array power2[ ].
- Similarly, store all the powers of 3 which are less than or equal to R in another array power3[].
- Initialise third array power23[] and store the pairwise product of each element of power2[] with each element of power3[] which are less than or equal to R.
- Now for any range [L, R], we will simply iterate over array power23[] and count the numbers in the range [L, R].
Below is the implementation of above approach:
C++
// C++ program to count the elements// in the range [L, R] whose prime// factors are only 2 and 3.#include <bits/stdc++.h>using namespace std;#define ll long long int// Function which will calculate the// elements in the given rangevoid calc_ans(ll l, ll r){ vector<ll> power2, power3; // Store the current power of 2 ll mul2 = 1; while (mul2 <= r) { power2.push_back(mul2); mul2 *= 2; } // Store the current power of 3 ll mul3 = 1; while (mul3 <= r) { power3.push_back(mul3); mul3 *= 3; } // power23[] will store pairwise product of // elements of power2 and power3 that are <=r vector<ll> power23; for (int x = 0; x < power2.size(); x++) { for (int y = 0; y < power3.size(); y++) { ll mul = power2[x] * power3[y]; if (mul == 1) continue; // Insert in power23][] // only if mul<=r if (mul <= r) power23.push_back(mul); } } // Store the required answer ll ans = 0; for (ll x : power23) { if (x >= l && x <= r) ans++; } // Print the result cout << ans << endl;}// Driver codeint main(){ ll l = 1, r = 10; calc_ans(l, r); return 0;} |
Java
// Java program to count the elements// in the range [L, R] whose prime// factors are only 2 and 3.import java.util.*;class GFG{// Function which will calculate the// elements in the given rangestatic void calc_ans(int l, int r){ Vector<Integer> power2 = new Vector<Integer>(), power3 = new Vector<Integer>(); // Store the current power of 2 int mul2 = 1; while (mul2 <= r) { power2.add(mul2); mul2 *= 2; } // Store the current power of 3 int mul3 = 1; while (mul3 <= r) { power3.add(mul3); mul3 *= 3; } // power23[] will store pairwise product of // elements of power2 and power3 that are <=r Vector<Integer> power23 = new Vector<Integer>(); for (int x = 0; x < power2.size(); x++) { for (int y = 0; y < power3.size(); y++) { int mul = power2.get(x) * power3.get(y); if (mul == 1) continue; // Insert in power23][] // only if mul<=r if (mul <= r) power23.add(mul); } } // Store the required answer int ans = 0; for (int x : power23) { if (x >= l && x <= r) ans++; } // Print the result System.out.print(ans + "\n");}// Driver codepublic static void main(String[] args){ int l = 1, r = 10; calc_ans(l, r);}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program to count the elements # in the range [L, R] whose prime # factors are only 2 and 3. # Function which will calculate the # elements in the given range def calc_ans(l, r): power2 = []; power3 = []; # Store the current power of 2 mul2 = 1; while (mul2 <= r): power2.append(mul2); mul2 *= 2; # Store the current power of 3 mul3 = 1; while (mul3 <= r): power3.append(mul3); mul3 *= 3; # power23[] will store pairwise # product of elements of power2 # and power3 that are <=r power23 = []; for x in range(len(power2)): for y in range(len(power3)): mul = power2[x] * power3[y]; if (mul == 1): continue; # Insert in power23][] # only if mul<=r if (mul <= r): power23.append(mul); # Store the required answer ans = 0; for x in power23: if (x >= l and x <= r): ans += 1; # Print the result print(ans); # Driver code if __name__ == "__main__": l = 1; r = 10; calc_ans(l, r); # This code is contributed by AnkitRai01 |
C#
// C# program to count the elements// in the range [L, R] whose prime// factors are only 2 and 3.using System;using System.Collections.Generic;class GFG{// Function which will calculate the// elements in the given rangestatic void calc_ans(int l, int r){ List<int> power2 = new List<int>(), power3 = new List<int>(); // Store the current power of 2 int mul2 = 1; while (mul2 <= r) { power2.Add(mul2); mul2 *= 2; } // Store the current power of 3 int mul3 = 1; while (mul3 <= r) { power3.Add(mul3); mul3 *= 3; } // power23[] will store pairwise product of // elements of power2 and power3 that are <=r List<int> power23 = new List<int>(); for (int x = 0; x < power2.Count; x++) { for (int y = 0; y < power3.Count; y++) { int mul = power2[x] * power3[y]; if (mul == 1) continue; // Insert in power23,] // only if mul<=r if (mul <= r) power23.Add(mul); } } // Store the required answer int ans = 0; foreach (int x in power23) { if (x >= l && x <= r) ans++; } // Print the result Console.Write(ans + "\n");}// Driver codepublic static void Main(String[] args){ int l = 1, r = 10; calc_ans(l, r);}}// This code is contributed by 29AjayKumar |
Javascript
<script>// JavaScript program to count the elements// in the range [L, R] whose prime// factors are only 2 and 3.// Function which will calculate the// elements in the given rangefunction calc_ans(l, r){ var power2 = [], power3 = []; // Store the current power of 2 var mul2 = 1; while (mul2 <= r) { power2.push(mul2); mul2 *= 2; } // Store the current power of 3 var mul3 = 1; while (mul3 <= r) { power3.push(mul3); mul3 *= 3; } // power23[] will store pairwise product of // elements of power2 and power3 that are <=r var power23 = []; for (var x = 0; x < power2.length; x++) { for (var y = 0; y < power3.length; y++) { var mul = power2[x] * power3[y]; if (mul == 1) continue; // Insert in power23][] // only if mul<=r if (mul <= r) power23.push(mul); } } // Store the required answer var ans = 0; power23.forEach(x => { if (x >= l && x <= r) ans++; }); // Print the result document.write( ans );}// Driver codevar l = 1, r = 10;calc_ans(l, r);</script> |
Output:
6
Time Complexity: O(log2(R) * log3(R)), as we are traversing in nested loops where we increment in multiple of 2 and 3.
Auxiliary Space: O(log2(R) * log3(R)), as we are using extra space.
Note: The approach can be further optimized. After storing powers of 2 and 3, the answer can be calculated using two pointers instead of generating all the numbers
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!
