6. Maths- part 2

8.) Print all divisors/factors-

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

Optimal: 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)

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

Optimal:  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:

Brute:    find all factors of n, then filter out prime numbers out of them.
 
Optimal:  finding all factors wale code ko hi modify krdo⭐


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

11.) Power Exponentiation-⭐


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

12) Print all prime numbers till n:

1. We use, Sieve of Eratosthenes
2. O( Nlog(logN) )
3.  After building this, we can tell if a number (from 2 to N) is prime or not in O(1)
-----------------------------------
Algo:- We just do some sort of pre computation
if elmt pe 1 hai:               uske multiples ko 0 krdo
if elmt pe already 0 hai:   skip 


-----------------------------------------------------------------------
Optimisations-
1. start j from (i*i) instead of (2*i)
2. i wale ke end ko bhi accordingly adjust krlo
---------------------------------------------------------------------------------------------------------------------

13.) Prime factorisation of n: 
(repeat wale bhi chahiye)⭐⭐
SPF- smallest prime factors

-----------------------------------------------------------
Method-1: Modified unique prime factors code

in the code of finding unique prime factors of n,
instead of saving the factor before entering the while loop,
now we will save every factor inside while loop
---------------------------------------------------------
Method-2:  Modified Sieve

instead of replacing multiples of i with 0, we will replace them with i itself.


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 prime numbers b/w L to R-
Brute:
L se R ke bich ke har number ko check kro ki prime hai ki nahi











------------------------------------------------------------
Better:
Sieve array mein dekhlo L to R mein kitne 1s hain...

------------------------------------------------------------
Alter:  Prefix Sum in sieve:-

1. in a Prefix array, store har index pe, ki sieve wale mein us index tak kitne 1s the
2. ans = prefix[R] - prefix[L-1]

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

Comments

Post a Comment

Popular posts from this blog

30.) DP on subsequences

Image
Subset sum = target✅⭐ Partition equal subset sum✅ Partition array into 2 subsets with min abs [sum(v1)-sum(v2) ]✅ Count subsets with sum k✅⭐ Count partitions with given diff✅ target sum✅ 0/1 knapsack✅⭐ min coins✅---->count min coins to be taken coin change-2--->count n(ways) of taking coins⭐✅ unbounded knapsack✅ rod cutting problem✅ ----------------------------------------------------------------------------------------------------------------------------- 2 ways to generate all subsequences- Power Set, or Recursion subset means subsequence in dsa ----------------------------------------------------------------------------------------------------------------------------- 1. Target Sum- QUES- return true if there exists a subset with sum equal to the target in the array... Soln assuming all array elements are positive  here f(n-1,target) will tell if there's a subsequence till n-1 index with sum = target 1.) RECURSIVE SOLN-        ( time: 2^n    ...
Read more

36. Graphs-2 (grid/traversal problems)

Image
 PROBLEMS ON BFS/ DFS:- no. of provinces          ✅ components rotten oranges            ⭐✅ multi source BFS no. of islands              ✅ BFS/ DFS flood fill                     ✅ BFS/ DFS no. of enclaves           ⭐✅ multi source   BFS/DFS no. of distinct islands ⭐✅ shape storing   BFS/ DFS surrounded regions    ✅ multi source   BFS/DFS 0/1 Matrix                  ⭐⭐✅ multi source BFS word ladder-1 , 2 ---------------------------------------------------------------------------------------------------------------------------- 1. No. of provinces Count total components in a graph time- O(N + V+2E)               space: O(N) --------------------------------------------------------------------------------...
Read more

19. Strings (LB)

Image
Character Array- 1. We use  1d character array  to simulate strings, e.g., char ch[10]; cin>>ch; 2. string ends with '\0' 3. cin with string works only if till space, tab or new line is absent in input... 4. work with character array just like a normal array, here only datatype is changed to char, else wise it is just an array -------------------------------------------- 5. In-Built functions- - int n = strlen(ch)   - strcmp(s1,s2)            // gives 0 if both strings are equal  - strcpy(dest,source)   // copies a string from dest to source -------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- STRING- It is a C++ STL 1. has dynamic size (can dynamically increase size when needed) 2. null terminator (\0) NOT required 3. Has built-in functions : - return s.size() - return s == "hello" - return s + "wor...
Read more