Maths Flashcards

1
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

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

A

Sieve of Eratosthenes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Time complexity of Sieve of Eratosthenes?

A

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

O(nloglogn)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Pseudo code for Sieve of Eratosthenes?

A
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Euclid’s algorithm for finding GCD?

A

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

            return GCD(b, a % b);
        }
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Formula for sum of integers from 1 to n

A

n*(n+1)/2

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Power function for calculating recursively

A

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

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Formula for next sequence element in array

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Total number of combinations for n items are?

A

2^n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

How to find LCM of two given numbers?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

How to find the number of digits in number?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

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

A

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

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

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

A

((n%K)+K)%K

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

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

A
int number = 0;
 while (char.IsNumber(s[index]))
 {           
          number = 10 * number + (s[index] - '0');
           \++index;
  }
  return number;
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What is the time complexity of Euclid’s algorithm?

A

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

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