6. Maths- part 2

8.) Print all divisors/factors-

Method-1 : 1 se n          tak ka loop chalake check divisibility of n with each i

Method-2 : 1 se sqrt(n) tak ka loop chalado and print i and n/i as per divisibility 

-----------------------------------------------------------------------------------------------------------------------------

9.) Prime number check-

prime number- has exactly 2 divisors (1 and itself)

Method-1 : 1 se n          tak dekhlo, ki it must have exactly 2 divisors...

Method-2:  1 se sqrt(n) tak dekhlo, ki it must have exactly 1 divisor...

above methods ki cond true hai toh prime hoga...else not...

-----------------------------------------------------------------------------------------------------------------------------

10.) Prime factors of n-

Method-1:    filter out primes out of all factors of n
 
Method-2:  1 se sqrt(N) tak save factors as per below code


------------------------------------------------------------------------------------------------------------

11.) Power Exponentiation-

-------------------------------------------------------------------------------------------------------------------------

12.) Sieve of erastosthenes-

(print all prime numbers till n)

if elmt pe 1 hai-- uske multiples ko 0 krdo 
if elmt pe 0 hai-- skip 
optimised code-
har baar j ko 2*i ki jagah i*i se start kro and i wale ke end ko bhi accordingly adjust krlo
---------------------------------------------------------------------------------------------------------------------

13.) Smallest prime factor (SPF), or Prime factorisation of n: 

(repeat wale bhi chahiye)⭐⭐

Method-1:
finding prime factors wale code mein hi ,while se pehle ke badle, while me ghusne k baad add kro ans me vo factor

Method-2:
2 ke multiples mein har jagah 2 rakhdo instead of 0, similarly do for 3,5, so on...

intution-
pre computation-

code-
30 ke prime factors k liye 30 pe jao in pre computation array uspe 2 milega toh ek factor toh 2 hai,  ab 30/2=15 pe jaao fir so on...














-----------------------------------------------------------------------------------------------------------------------------
14.) Count primes b/w L to R-
Brute:


Better:
                sieve lagake prime array banalo aur us array me L to R mein kitne 1 hain ye dekhlo

 Optimal:
                                                                prefix sum in sieve-
har index pe store krlenge ki sieve wale mein us index tak kitne 1s hain...
--------------------------------------------------------------------------------------------------------------------

Comments

Post a Comment

Popular posts from this blog

18. greedy algorithm

Image
assign greedily  like sabse kam distribute kro starting mein bade number last k liye bacha k rakho we use 2 pointer here ---------------------------------------------------------------------------------------------------------------------------- if smj ni aara ki konsa stl use kru, u can even solve ques with few varibles also. ----------------------------------------------------------------------------------------------------------------------------- Shortest Job First Problem Jump game 1 Jump game 2 Job Sequencing problem N Meetings in a room Insert Intervals Min platforms Valid parenthesis Candy Fractional Knapsack ------------------------------------------------------------------------------------------------------------------------ Shortest Job First Problem- --------------------------------------------------------------------------------------------------------------------------- JUMP GAME-1 --------------------------------------------------------------------------------------...
Read more

19. strings (LB)

Image
strings are 1d character array. e.g., char ch[10]; cin>>ch; string ends with '\0' cin with string works only if till space, tab or new line is absent in input... ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- STRING- dynamic size no null termination in built functions --------------------------------------------------- ------------------------------------------------------------------------- --------...
Read more

17. BINARY SEARCH on 2d arrrays

Image
 1.)   ROW WITH MAX 1s- given each row is sorted. BRUTE - simple 2 loops OPTIMAL - binary search lagalo to find index of 1st occurence of 1 in a row -------------------------------------------------------------------------------------------------------------- 2.) Search in 2d Matrix-(sorted rows consecutive) BRUTE - use 2 loops BETTER - check for only that row jisme target is between a[i][0] and a[i][c-1]  OPTIMAL - 2d array ko hypothetically 1d me karke binary search lagalo --------------------------------------------------------------------------------------------------------------- 3.) Search in matrix(sorted row and col but not consecutive) BETTER- use binary search for every row OPTIMAL -(time: N+M) --------------------------------------------------------------------------------------------------------------- 4.) Peak elements in matrix- BRUTE- 1.) we can do linear search and for each element compare with its 4 neighbours 2.) Or, we can find max element in matrix BET...
Read more