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

Binary Search Algorithm!

Binary search is a searching algorithm used in a sorted array by repeatedly dividing the search interval in half. The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(log N)¹. Here's how it works: 1. Compare x with the middle element. 2. If x matches with the middle element, we return the mid index. 3. Else If x is greater than the mid element, then x can only lie in the right half subarray after the mid element. So we recur for the right half. 4. Else (x is smaller) recur for the left half. This process continues until the element is found or the subarray is empty. Look at the array, it is sorted and if we want to find 7 in this array easily by implementing binary search algorithm. We can find it in O(logn) time. While a linear search will take O(n) time which is very long time. So, if an array is sorted we always use Binary search. Algorithm: int main() { optimize(); int arr[]= {1,4,5,8,10,26...

Easiest way to find out which power of number is big?

If you are given two number with its power and told you which number is big. How do you calculate it. For, instance you would say binary exponentiation technique. But this is bit harder when the test case number is bigger. There is also an easy way to solve this problem. Suppose you are given 2^18 and 6^12. Then, you just take logarithm in both numbers. Then it will become 18*log2 and 12*log6. Logarithm function will break this number and make it a little number. which can be compare easily. But for this you have to Double number type, or you will get an error message. Problem: Problem - 987B - Codeforces Code: void solve() { ll a,b; cin>>a>>b; double num1 = b*log(a); double num2 = a*log(b); if(num1==num2) cout<<'='<<endl; else if(num1>num2) cout<<'>'<<endl; else cout<<'<'<<endl; }

Two Pointer Technique

The two-pointer technique is a simple and effective technique that is used in competitive programming. It helps programmer to efficiently solve array problem. In two-pointer we take two pointer at the start and the end. That pointers started to iterate the whole array and solve problem according to a programmer. Suppose, we have an array n which consists m number of values. Now, if we want to sum all the element of the array then we have to iterate the whole array and sum all the element. Which will take O(n) time. n = [4, 5, 2, 4, 9, 4] But, in two-pointer technique we can solve this problem in O(n/2) time. Which is more efficient than traditional way. In the code, we used two variable st which point at first element of the array and en which point at the last element of the array. After this, we take a while loop which condition is st should be less than en. If the condition does not meet the value, then loop will break. In the loop, we summed the first value and last value that are ...

Ryansblog

Search This Blog