Find all factors of the number ?
A number is always divisible by 1 and itself. The smallest factor a number can have is 2, while largest factor would be n/2. But as a * b = number n, were a and b are co-efficient, the pairs of numbers will be duplicated after a = b, i.e. square-root of n. Hence we only need to loop till square-root of n, and add both i and n/i to the list of factors.
Verify if number is a prime number ?
To verify a prime number we only need to loop through from 2 to square-root of number n. As the number n to be non-prime there must be factors "a" and "b" such that a = n / b, i.e. a * b = n. As we observe for example number 36, the factor pairs {1,36} {2,18} {3,12} {4,9} {6,6} {9,4} {12,3} {18,2} {36,1} are repeated after {6,6} which is after square-root of 36, i.e. 6. Hence after square-root of n, the numbers would be either repeated factor-pairs, multiple of other prime numbers.
Also 1 is not regarded as a prime number.
Fibonacci Sequence
F(n) = { F(n - 1) + F(n - 2) if n > 1
{ n if n = 0,1 }
0 1 1 2 3 5 8 ...
The first two terms of the series are 0, 1.
Using Recursion: if(n <= 1) return n; return fibonacci(n-1) + fibonacci(n-2)
Recursion: Exponential Time
Fibonacci Sequence Recursion: O(2^n)
Iteration: Here we need three variables, the previousNumber, the currentNumber and a temp Number as we cannot assign the new value to currentNumber directly because, we have to first move currentNumber's value to previousNumber.
System.out.print(previousNumber + ", ");
for (int i = 1; i < n; i++) {
newNumber = currentNumber + previousNumber;
previousNumber = currentNumber;
currentNumber = newNumber;
System.out.print(currentNumber + ", ");
}
Modular Exponentiation
Calculate: x^n mod M
Since integer is 32 bit, with 1 bit reserved for sign, the range of integer is -2^31 to 2^31, hence calculating x^n directly will not fit many cases within integer range.
Since (a * b) % M = {(a % M) * (b % M)} % M
x^n % M = (x * x^n-1) % M
= {(x % M) * (x^n-1 % M)} % M
When n is even, {(x^n/2 % M) * (x^n/2 % M)} % M
Time complexity is O(log n)
Power(x,n) i.e. x^n
x^n = { x^n/2 * x^n/2 if n is even
x * x^n-1 if n is odd
1 if n=0 }
To calculate the time complexity, use the variance of the number being updated and passed to the recursive function.
T(n) = T(n/2) + C
T(n) = T(n/2^k) + K*C assuming this is done k times.
Hence k is log2(n) which is the time complexity.
Find all factors of the number:
12 = {1,2,3,4,6,12}
Trial Division were we try to divide the number with all the numbers from 1 to n itself.
But 1 and the number itself are its factors. Also since the smallest factor of the number is 2 and largest factor is n/2, there are no factors of the number above n/2. Also if a * b = n, assuming a.b are factors, then when a > sqrt n, then b < sqrt n. Further when a = sqrt n, then a = b = sqrt n. Hence only search factor till square root of number, as remaining are just number/factor.
Divide all the numbers starting from 2 to square-root of n, and add [current-no] with (n / [current-no]) to the factors list. Numbers 1 and n are already added to factors list.
Time complexity is O(sqrt n)
24 = 3 * 2 * 2 * 2
Start dividing the number n by smallest number (starting with 2) such that the remainder is 0. Continue dividing the quotient from previous division until the remainder is non-zero, then select the next number for division of the quotient. The loop continues selecting next smallest number (i) until the (i) becomes greater than square-root of quotient, which indicates that the quotient is a prime number. Since we already know that there cannot be any factors for a number (quotient here) after square-root of that number.
Time complexity is O(sqrt n)
How do implement Sieve of Eratosthenes Algorithms for Prime Number?
How to check if a given year is a leap year in Java?
How to convert a decimal number to binary in Java?
How to reverse given Integer in Java?
How to find the largest prime factor of a given integral number?
How to print Floyd’s triangle?
How to print Pascal’s triangle? (solution)
How to calculate the square root of a given number?
No comments:
Post a Comment