Given two integers N and M, the task is to print all elements in the range [N, M] having at least one odd divisor.
Examples:
Input: N = 2, M = 10
Output: 3 5 6 7 9 10
Explanation:
3, 6 have an odd divisor 3
5, 10 have an odd divisor 5
7 have an odd divisor 7
9 have two odd divisors 3, 9
Input: N = 15, M = 20
Output: 15 17 18 19 20
Naive Approach:
The simplest approach is to loop through all numbers in the range [1, N], and for every element, check if it has an odd divisor or not.
Time Complexity: O(N3/2)
Efficient Approach:
To optimize the above approach, we need to observe the following details:
- Any number which is a power of 2, does not have any odd divisors.
- All other elements will have at least one odd divisors
Illustration:
In the range [3, 10], the elements which have at least one odd divisors are {3, 5, 6, 7, 9, 10} and {4, 8} does not contain any odd divisors.
Follow the steps below to solve the problem:
- Traverse the range [N, M] and check for each element if any of its set bit is set in the previous number or not, that is check whether i & (i – 1) is equal to 0 or not.
- If so, then the number is a power of 2 and is not considered. Otherwise, print the number as it is not a power of 2 and has at least one odd divisor.
Below is the implementation of the above approach.
C++
// C++ program to print all numbers // with least one odd factor in the // given range #include <bits/stdc++.h> using namespace std; // Function to prints all numbers // with at least one odd divisor int printOddFactorNumber( int n, int m) { for ( int i = n; i <= m; i++) { // Check if the number is // not a power of two if ((i > 0) && ((i & (i - 1)) != 0)) cout << i << " " ; } } // Driver Code int main() { int N = 2, M = 10; printOddFactorNumber(N, M); return 0; } |
Java
// Java program to print all numbers // with least one odd factor in the // given range class GFG{ // Function to prints all numbers // with at least one odd divisor static int printOddFactorNumber( int n, int m) { for ( int i = n; i <= m; i++) { // Check if the number is // not a power of two if ((i > 0 ) && ((i & (i - 1 )) != 0 )) System.out.print(i + " " ); } return 0 ; } // Driver Code public static void main(String[] args) { int N = 2 , M = 10 ; printOddFactorNumber(N, M); } } // This code is contributed // by shivanisinghss2110 |
Python3
# Python3 program to print all numbers # with least one odd factor in the # given range # Function to prints all numbers # with at least one odd divisor def printOddFactorNumber(n, m): for i in range (n, m + 1 ): # Check if the number is # not a power of two if ((i > 0 ) and ((i & (i - 1 )) ! = 0 )): print (i, end = " " ) # Driver Code N = 2 M = 10 printOddFactorNumber(N, M) # This code is contributed by Vishal Maurya |
C#
// C# program to print all numbers // with least one odd factor in the // given range using System; class GFG{ // Function to prints all numbers // with at least one odd divisor static int printOddFactorNumber( int n, int m) { for ( int i = n; i <= m; i++) { // Check if the number is // not a power of two if ((i > 0) && ((i & (i - 1)) != 0)) Console.Write(i + " " ); } return 0; } // Driver Code public static void Main() { int N = 2, M = 10; printOddFactorNumber(N, M); } } // This code is contributed // by Code_Mech |
Javascript
<script> // JavaScript program to implement // the above approach // Function to prints all numbers // with at least one odd divisor function printOddFactorNumber(n, m) { for (let i = n; i <= m; i++) { // Check if the number is // not a power of two if ((i > 0) && ((i & (i - 1)) != 0)) document.write(i + " " ); } return 0; } // Driver code let N = 2, M = 10; printOddFactorNumber(N, M); // This code is contributed by susmitakundugoaldanga. </script> |
3 5 6 7 9 10
Time Complexity: O(N)
Auxiliary Space: O(1)
Approach#2: Using prime factorization
This approach uses a function prime_factors to find the prime factors of a given number. It then uses another function elements_in_range_with_odd_divisors to iterate over the given range n to m, find the prime factors of each number and check if any of its factors are odd. If any of the factors are odd, the number is appended to the result list. Finally, the result list is converted to a space-separated string using the join() function.
Algorithm
1. Define a function prime_factors(num) that takes a number as input and returns its prime factors as a set.
2. Define a function elements_in_range_with_odd_divisors(n, m) that takes a range n to m as input.
3. Initialize an empty list result to store the numbers that have at least one odd divisor.
4. Iterate over the range n to m using a for loop.
5. For each number in the range, find its prime factors using the prime_factors function.
6. Check if any of the prime factors are odd using the any() function.
7. If any of the prime factors are odd, append the number to the result list.
8. Convert the result list to a space-separated string using the join() function.
9. Return the string.
C++
#include <iostream> #include <vector> #include <set> #include <cmath> // Function to find the prime factors of a number and store them in a set std::set< int > prime_factors( int num) { std::set< int > factors; // Divide by 2 until it's no longer divisible by 2 while (num % 2 == 0) { factors.insert(2); num /= 2; } // Check odd factors starting from 3 for ( int i = 3; i <= sqrt (num); i += 2) { while (num % i == 0) { factors.insert(i); num /= i; } } // If the remaining number is greater than 2, it's also a factor if (num > 2) { factors.insert(num); } return factors; } // Function to find and return elements in a given range with odd prime factors std::string elements_in_range_with_odd_divisors( int n, int m) { std::vector< int > result; // Loop through the range [n, m] for ( int i = n; i <= m; ++i) { // Find the prime factors of the current number std::set< int > factors = prime_factors(i); bool hasOddFactor = false ; // Check if any factor is odd for ( int factor : factors) { if (factor % 2 == 1) { hasOddFactor = true ; break ; } } // If the number has an odd factor, add it to the result vector if (hasOddFactor) { result.push_back(i); } } // Convert the result vector to a string for printing std::string resultStr; for ( int x : result) { resultStr += std::to_string(x) + " " ; } return resultStr; } // Main function int main() { // Set the range [n, m] int n = 2; int m = 10; // Call the function and print the result std::string result = elements_in_range_with_odd_divisors(n, m); std::cout << result << std::endl; return 0; } |
Python3
def prime_factors(num): factors = [] while num % 2 = = 0 : factors.append( 2 ) num / / = 2 for i in range ( 3 , int (num * * 0.5 ) + 1 , 2 ): while num % i = = 0 : factors.append(i) num / / = i if num > 2 : factors.append(num) return set (factors) def elements_in_range_with_odd_divisors(n, m): result = [] for i in range (n, m + 1 ): factors = prime_factors(i) if any (factor % 2 = = 1 for factor in factors): result.append(i) return " " .join( str (x) for x in result) n = 2 m = 10 print (elements_in_range_with_odd_divisors(n,m)) |
Javascript
// Function to find the prime factors of a number and store them in a Set function primeFactors(num) { const factors = new Set(); // Divide by 2 until it's no longer divisible by 2 while (num % 2 === 0) { factors.add(2); num /= 2; } // Check odd factors starting from 3 for (let i = 3; i <= Math.sqrt(num); i += 2) { while (num % i === 0) { factors.add(i); num /= i; } } // If the remaining number is greater than 2, it's also a factor if (num > 2) { factors.add(num); } return factors; } // Function to find and return elements in a given range with odd prime factors function elementsInRangeWithOddDivisors(n, m) { const result = []; // Loop through the range [n, m] for (let i = n; i <= m; ++i) { // Find the prime factors of the current number const factors = primeFactors(i); let hasOddFactor = false ; // Check if any factor is odd for (let factor of factors) { if (factor % 2 === 1) { hasOddFactor = true ; break ; } } // If the number has an odd factor, add it to the result array if (hasOddFactor) { result.push(i); } } // Convert the result array to a string for printing return result.join( " " ); } // Main function function main() { // Set the range [n, m] const n = 2; const m = 10; // Call the function and print the result const result = elementsInRangeWithOddDivisors(n, m); console.log(result); } // Call the main function main(); |
3 5 6 7 9 10
The time complexity of the code is O((m-n) * sqrt(m))
Space complexity is O(m).
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!