Module 1 — Time & Space Complexity, Mathematical and String Algorithms (Java Solutions)
1. GCD of two numbers (Euclid) [Easy]
Solution approach: iterative Euclidean algorithm.
Java code:
public static long gcd(long a, long b) {
while (b != 0) {
long t = a % b;
a = b;
b = t;
}
return a;
}
Reference: [Link]
2. LCM using GCD [Easy]
Use lcm = a / gcd(a,b) * b (use long to avoid overflow).
public static long lcm(long a, long b) {
return a / gcd(a,b) * b;
}
Reference: [Link]
3. Sieve of Eratosthenes [Easy]
Generate primes up to N in O(N log log N).
public static boolean[] sieve(int n) {
boolean[] isPrime = new boolean[n+1];
[Link](isPrime, true);
isPrime[0]=isPrime[1]=false;
for (int p=2;p*p<=n;p++) if(isPrime[p])
for(int q=p*p;q<=n;q+=p) isPrime[q]=false;
return isPrime;
}
Reference: [Link]
4. Segmented Sieve [Medium]
Sieve primes in [L,R] using base primes up to sqrt(R).
// Outline: get base primes via sieve(sqrtR), then mark segments.
Reference: [Link]
5. Modular Exponentiation (binary exponentiation) [Easy]
Fast power mod.
public static long modPow(long a,long e,long mod){
long res=1%mod;
a%=mod;
while(e>0){
if((e&1)==1) res=(res*a)%mod;
a=(a*a)%mod;
e>>=1;
}
return res;
}
Reference: [Link]
6. Modular Inverse (Fermat) [Medium]
When mod is prime: inverse = a^(mod-2) % mod using modPow.
public static long modInv(long a,long mod){return modPow(a,mod-2,mod);}
Reference: [Link]
7. Naive pattern search [Easy]
Slide pattern and compare.
public static List<Integer> naive(String s,String p){
List<Integer> ans=new ArrayList<>();
for(int i=0;i+[Link]()<=[Link]();i++){
if([Link](i,i+[Link]()).equals(p)) [Link](i);
}
return ans;
}
Reference: [Link]
8. KMP (Knuth-Morris-Pratt) [Medium]
Build lps array and search.
public static int[] buildLPS(String p){
int m=[Link]();int[] lps=new int[m];
for(int i=1,len=0;i<m;){
if([Link](i)==[Link](len)) lps[i++]=++len;
else if(len>0) len=lps[len-1]; else lps[i++]=0;
}
return lps;
}
public static List<Integer> kmp(String s,String p){
List<Integer> res=new ArrayList<>(); int n=[Link](),m=[Link]();
int[] lps=buildLPS(p); int i=0,j=0;
while(i<n){
if([Link](i)==[Link](j)){i++;j++; if(j==m){[Link](i-j); j=lps[j-1];}}
else if(j>0) j=lps[j-1]; else i++;
}
return res;
}
Reference: [Link]
9. Rabin-Karp (rolling hash) [Medium]
Use rolling polynomial hash with mod to search; check collisions.
// Outline: compute hash of pattern and rolling hash of text windows; compare and verify.
Reference: [Link]
10. Z-algorithm [Medium]
Compute Z-array to find matches.
public static int[] zFunction(String s){
int n=[Link](); int[] z=new int[n];
for(int i=1,l=0,r=0;i<n;i++){
if(i<=r) z[i]=[Link](r-i+1,z[i-l]);
while(i+z[i]<n && [Link](z[i])==[Link](i+z[i])) z[i]++;
if(i+z[i]-1>r){l=i;r=i+z[i]-1;}
}
return z;
}
Reference: [Link]
11. Longest palindromic substring (Manacher) [Hard]
Manacher's algorithm O(n). Outline: transform string with separators, compute radii.
// Due to space, link provides full code; implement Manacher when needed.
Reference: [Link]
12. String hashing: count distinct substrings [Hard]
Use rolling hash of all suffixes and collect in HashSet. Or suffix array + LCP for efficiency.
// Outline provided in link.
Reference: [Link]