Skip to main content

Find out all divisor in efficient way!

1. Brute force approach:

  In this process, we use a for loop and iterate the whole 1 to n number. Then, we find out all the divisors by one by one. It is not a optimal solution for this problem. Because, it will take O(n) time to find out all divisors.

int main()
{
    optimize();
    ll n;
    cin>>n;
    for(ll i=1; i<=n; i++)
    {
        if(n%2==0) cout<<i<<" ";
    }
    cout<<endl;
    return 0;
}


Time complexity: O(n)

2. SQRT approach:

  In this process, we only iterate in the loop by half of the numbers. Because, if we see we don't need to go through whole n numbers.

int main()
{
    optimize();
    ll n;
    cin>>n;
    for(ll i=1; i * i<=n; i++)
    {
        if(n%2==0) cout<<i<<" "<<n/i<<endl;
    }
    return 0;
}

Time Complexity: O(sqrt(n))

   
  



Comments

Post a Comment

Popular posts from this blog

Rotated Array(Modified Binary Search)

  A modified binary search is an algorithm that can be used to find an element in a sorted array by using a different base or condition than the standard binary search. It is an extension of the bitwise binary search and has a similar running time of O(log N) . There are different ways to modify the binary search algorithm, such as using a different number base, finding the minimum element in a rotated and sorted array, or comparing the input element with the first, last and middle elements of the array. Today we will look at rotated array problems. A rotated array is an array that is sorted in ascending order but shifted to the right by some unknown number of positions. For example, [0,1,2,4,5,6,7] is a sorted array and [4,5,6,7,0,1,2] is a rotated array with 4 positions shifted. A rotated array can also be seen as two sorted subarrays concatenated together. For example, [4,5,6,7] and [0,1,2] are two sorted subarrays that form the rotated array [4,5,6,7,0,1,2]. There are two very ...
Post a Comment
Read more

Two Pointer Problems

Here we have given some important two pointer problems below: 1. Valid Palindrome: A phrase is a  palindrome  if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers. Given a string  s , return  true  if it is a  palindrome , or  false  otherwise .  -> Solution: class Solution { public:     bool isPalindrome(string s) {       int low=0;       int high=s.length()-1;       while(low<high){           while(!iswalnum(s[low]) && low<high){               low++;           }           while(!iswalnum(s[high]) && low<high){               high--;           } ...
Post a Comment
Read more