Given two integers L and R, the task is to find the count of numbers in the range [L, R] which have only 2 or 7 as their prime factors.
Examples:
Input: L = 0, R = 0
Output: 0
Explanation: 0 is not divisible by 2 or 7Input: L = 0, R = 2
Output: 1
Explanation: Only 2 is the number between the range which has 2 as a factor, hence count is 1.Input: L = 1, R = 15
Output: 5
Explanation: 2, 4, 7, 8 & 14 are the numbers which has factors as 2 or 7, hence, count is 5
Naive Approach: The simple approach is to generate all prime factors of each number in the range [L, R] and check if the factors are only 2 or 7.
Follow the steps to solve the problem:
- Traverse from i = L to R:
- Store all prime factors of i in a vector (say factors).
- Traverse the vector to see if factors other than 2 or 7 are present or not.
- If i is divisible by only 2 or 7 then increment count otherwise.
- Return pair of special and regular as the final answer.
Below is the implementation for the above approach:
C++14
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// Function to find regular or special numberspair<int,int> SpecialorRegular(int L, int R){ int regular = 0, special = 0, temp, i, j; vector<int>factors; // Base cases if(L > R || L < 0|| R < 0) return {-1, -1}; else if(R < 2) regular += R - L + 1; else regular += 2 - L; L = 2; for(i = L; i <= R; i++){ temp = i; factors.clear(); for(j = 2; j * j <= i; j++) { while(temp % j == 0){ factors.push_back(j); temp /= j; } } if(temp > 1) factors.push_back(temp); for(j = 0; j < factors.size(); j++){ if(factors[j] != 7 && factors[j] != 2) break; } if(j == factors.size()) special++; else regular++; } return {special, regular};}//Function to printvoid print(int L, int R){ pair<int, int>ans = SpecialorRegular(L, R); cout << ans.first;}//Driver codeint main(){ int L = 0; int R = 2; // Function Call print(L, R); return 0;} |
Java
// Java program for above approachimport java.util.ArrayList;class GFG { // Function to find regular or special numbers static int[] SpecialorRegular(int L, int R) { int regular = 0, special = 0, temp, i, j; ArrayList<Integer> factors = new ArrayList<Integer>(); // Base cases if (L > R || L < 0 || R < 0) { int[] pair = { -1, -1 }; return pair; } else if (R < 2) regular += R - L + 1; else regular += 2 - L; L = 2; for (i = L; i <= R; i++) { temp = i; factors.clear(); for (j = 2; j * j <= i; j++) { while (temp % j == 0) { factors.add(j); temp /= j; } } if (temp > 1) factors.add(temp); for (j = 0; j < factors.size(); j++) { if ((factors.get(j) != 7) && (factors.get(j) != 2)) break; } if (j == factors.size()) special++; else regular++; } int[] pair = { special, regular }; return pair; } // Function to print static void print(int L, int R) { int[] ans = SpecialorRegular(L, R); System.out.print(ans[0]); } // driver code public static void main(String[] args) { int L = 0; int R = 2; // Function Call print(L, R); }}// This code is contributed by phasing17 |
Python3
# Python3 code for the above approach# Function to find regular or special numbersdef SpecialorRegular(L, R): regular, special = 0, 0 factors = [] # base cases if L > R or L < 0 or R < 0: return [-1, -1] elif R < 2: regular += R - L + 1 else: regular += 2 - L L = 2 for i in range(L, R + 1): temp = i factors = [] for j in range(2, 1 + int(i ** 0.5)): while not temp % j: factors.append(j) temp //= j if temp > 1: factors.append(temp) j = 0 while j < len(factors): if factors[j] != 7 and factors[j] != 2: break j += 1 if j == len(factors): special += 1 else: regular += 1 return [special, regular] # Function to printdef prints(L, R): ans = SpecialorRegular(L, R) print(ans[0])# Driver codeL, R = 0, 2# Function Callprints(L, R)# This code is contributed by phasing17 |
C#
// C# code for the above approachusing System;using System.Collections.Generic;class GFG{ // Function to find regular or special numbers static Tuple<int,int> SpecialorRegular(int L, int R) { int regular = 0, special = 0, temp, i, j; List<int>factors=new List<int>(); // Base cases if(L > R || L < 0|| R < 0) return new Tuple<int,int>(-1,-1); else if(R < 2) regular += R - L + 1; else regular += 2 - L; L = 2; for(i = L; i <= R; i++){ temp = i; factors.Clear(); for(j = 2; j * j <= i; j++) { while(temp % j == 0){ factors.Add(j); temp /= j; } } if(temp > 1) factors.Add(temp); for(j = 0; j < factors.Count; j++){ if(factors[j] != 7 && factors[j] != 2) break; } if(j == factors.Count) special++; else regular++; } return new Tuple<int,int>(special, regular); } // Function to print static void print(int L, int R) { Tuple<int, int>ans = SpecialorRegular(L, R); Console.Write(ans.Item1); } // Driver code static void Main(string[] args) { int L = 0; int R = 2; // Function Call print(L, R); }} |
Javascript
<script> // JavaScript code for the above approach // Function to find regular or special numbers const SpecialorRegular = (L, R) => { let regular = 0, special = 0, temp, i, j; let factors = []; // Base cases if (L > R || L < 0 || R < 0) return [-1, -1]; else if (R < 2) regular += R - L + 1; else regular += 2 - L; L = 2; for (i = L; i <= R; i++) { temp = i; factors = []; for (j = 2; j * j <= i; j++) { while (temp % j == 0) { factors.push(j); temp = parseInt(temp / j); } } if (temp > 1) factors.push(temp); for (j = 0; j < factors.length; j++) { if (factors[j] != 7 && factors[j] != 2) break; } if (j == factors.length) special++; else regular++; } return [special, regular]; } // Function to print const print = (L, R) => { let ans = SpecialorRegular(L, R); document.write(ans[0]); } // Driver code let L = 0; let R = 2; // Function Call print(L, R);// This code is contributed by rakeshsahni</script> |
Output
1
Time Complexity: O((R – L)(3 / 2))
Auxiliary Space: O(log R)
Efficient Approach: The problem can be solved more efficiently follow the mentioned observation:
Observation:
Generate all the numbers of form 2*k or 7*k or 2*7*k using recursion where k is also in one of the previous three forms.
Follow the steps to solve the problem:
- Initialize an unordered map as visited to store the numbers visited already and count as 0 to store the count of such numbers.
- Prepare a recursive function to generate the numbers as shown in the observation.
- If a generated number (say temp) is:
- Within the range [L, R] and not already visited then mark it as visited and increment count.
- Exceeds R or is already visited return from that recursion and try other options.
- Return the count as the final required answer.
Below is the implementation for the above approach:
C++14
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;int special = 0;unordered_map<int, bool> visited;// Function to find special numbersvoid countSpecial(int L, int R, int temp){ // Base cases if (L > R) { special = -1; return; } else if (L < 0 || R < 0) { special = -1; return; } else if (temp > R) return; if (L <= temp && temp <= R && temp != 1 && !visited[temp]) { special++; visited[temp] = 1; } countSpecial(L, R, temp * 2); countSpecial(L, R, temp * 7);}// Print functionvoid print(int L, int R){ countSpecial(L, R, 1); if (special == -1) cout << -1 << " " << -1; else cout << special;}// Driver codeint main(){ int L = 0; int R = 2; // Function call print(L, R); return 0;} |
Java
// Java program for above approachimport java.io.*;import java.util.*;import java.util.ArrayList;class GFG {static int special = 0;private static HashMap<Integer, Boolean> visited = new HashMap<>(); // Function to find special numbersstatic void countSpecial(int L, int R, int temp){ // Base cases if (L > R) { special = -1; return; } else if (L < 0 || R < 0) { special = -1; return; } else if (temp > R) return; if (L <= temp && temp <= R && temp != 1 && !visited.containsKey(temp)) { special++; visited.put(temp,true); } countSpecial(L, R, temp * 2); countSpecial(L, R, temp * 7);}// Function to printstatic void print(int L, int R){ countSpecial(L, R, 1); if (special == -1) System.out.print("-1 -1"); else System.out.print(special);}// driver codepublic static void main(String[] args){ int L = 0; int R = 2; // Function Call print(L, R);}}// This code is contributed by Pushpesh Raj |
Python3
# Python code for the above approachspecial = 0visited = {}# Function to find special numbersdef countSpecial(L, R, temp): global special, visited # Base cases if (L > R): special = -1 return elif (L < 0 or R < 0): special = -1 return elif (temp > R): return if (L <= temp and temp <= R and temp != 1 and temp not in visited): special += 1 visited[temp] = 1 countSpecial(L, R, temp * 2) countSpecial(L, R, temp * 7)# Print functiondef Print(L, R): countSpecial(L, R, 1) if (special == -1): print("-1" + " " + "-1") else: print(special)# Driver codeL = 0R = 2# Function callPrint(L, R)# This code is contributed by shinjanpatra |
C#
// C# program for above approachusing System;using System.Collections.Generic;class GFG { static int special = 0; private static Dictionary<int, bool> visited = new Dictionary<int, bool>(); // Function to find special numbers static void CountSpecial(int L, int R, int temp) { // Base cases if (L > R) { special = -1; return; } else if (L < 0 || R < 0) { special = -1; return; } else if (temp > R) return; if (L <= temp && temp <= R && temp != 1 && !visited.ContainsKey(temp)) { special++; visited[temp] = true; } CountSpecial(L, R, temp * 2); CountSpecial(L, R, temp * 7); } // Function to print static void Print(int L, int R) { CountSpecial(L, R, 1); if (special == -1) Console.WriteLine("-1 -1"); else Console.WriteLine(special); } // driver code public static void Main(string[] args) { int L = 0; int R = 2; // Function Call Print(L, R); }}// This code is contributed by Utkarsh |
Javascript
<script> // JavaScript code for the above approach let special = 0; let visited = new Map(); // Function to find special numbers function countSpecial(L, R, temp) { // Base cases if (L > R) { special = -1; return; } else if (L < 0 || R < 0) { special = -1; return; } else if (temp > R) return; if (L <= temp && temp <= R && temp != 1 && !visited.has(temp)) { special++; visited.set(temp,1); } countSpecial(L, R, temp * 2); countSpecial(L, R, temp * 7); } // Print function function print(L, R) { countSpecial(L, R, 1); if (special == -1) document.write("-1" + " " + "-1"); else document.write(special); } // Driver code let L = 0; let R = 2; // Function call print(L, R); // This code is contributed by Potta Lokesh </script> |
Output
1
Time Complexity: O(R)
Auxiliary Space: O(R – L)
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!
Share your thoughts in the comments