Maths

Question 1

What is the the trial division method to find number is prime or not?

Answer 1

To find number is prime or not , we need to divide all the numbers less than number till 2. If it is divisible by any number(number%(n-1)==0) then its not prime number.

Trial division method divide number by all numbers less than or equal to sqrt of number rather than dividing by all the numbers

Question 2

What is the most efficient way of finding prime numbers smaller than n(where n is smaller then one million or so)?

Answer 2

Sieve of Eratosthenes

Question 3

Time complexity of Sieve of Eratosthenes?

Answer 3

https://www.youtube.com/watch?v=eKp56OLhoQs

O(nloglogn)

Question 4

Pseudo code for Sieve of Eratosthenes?

Answer 4

https://www.cs.cmu.edu/~scandal/cacm/node8.html
procedure PRIME(n):
let A be an array of length n
set all elements of A to true
for i from 2 to √n
     begin 
        ifA[i] is True
        then set all the multiples of i up to n to  FALSE 
     end

Question 5

Euclid’s algorithm for finding GCD?

Answer 5

public int GCD(int a, int b)
{
if (b == 0)
return a;

            return GCD(b, a % b);
        }

Question 6

Formula for sum of integers from 1 to n

Answer 6

n*(n+1)/2

Question 7

Power function for calculating recursively

Answer 7

power(x, y / 2) * power(x, y / 2) for even

x * power(x, y / 2) * power(x, y / 2); for odd

Question 8

How to calculate common difference between the successive elements of the sequence

Answer 8

https://www.techiedelight.com/find-missing-term-sequence-ologn-time/
(last element in sequence -first element in sequence)/total elements in sequence

Question 9

Formula for next sequence element in array

Answer 9

a[i]=d*i + a[0]
where i is ith element or the index in array
and d is the common difference

0 1 2 3 4 5
5 7 9 11 13 15

a[5]=2*5 + 5

Question 10

Total number of combinations for n items are?

Answer 10

2^n

Question 11

How to find LCM of two given numbers?

Answer 11

https://www.youtube.com/watch?v=8E1i5l6h22c
(GCDLCM)=(ab)
LCM=(a*b)/(GCD)

Question 12

How to find the number of digits in number?

Answer 12

(int)Math.Floor(Math.Log10(n) + 1);

Question 13

Formula for quickly incrementing/decrementing digit by 1 ,assuming that digits are in range 0 to 9?

Answer 13

(10+n+1)%10 where n is in range 0 to 9

(10+n-1)%10 where n is in range 0 to 9

Question 14

How to calculate the remainder for the negative number n when taking mod with negative number?

Answer 14

((n%K)+K)%K

Question 15

Given a string s=’123’ , how to convert it into number without using build-in function?

Answer 15

int number = 0;
 while (char.IsNumber(s[index]))
 {           
          number = 10 * number + (s[index] - '0');
           \++index;
  }
  return number;

Question 16

What is the time complexity of Euclid’s algorithm?

Answer 16

https://www.youtube.com/watch?v=7HCd074v8g8

O(logb) where b is the smaller number between a and b