Time and Space Complexity

### Constant Time: O(1)

// Accessing the first element (no matter input size)

int getFirst(int[] arr) {

return arr[0];
}

### Logarithmic Time: O(log n)

// Binary search in sorted array

int binarySearch(int[] arr, int x) {

int left = 0, right = [Link] - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == x) return mid;
if (arr[mid] < x) left = mid + 1;
else right = mid - 1;
}
return -1;
}

### Linear Time: O(n)

// Sum all array elements

int sum(int[] arr) {

int total = 0;
for (int i = 0; i < [Link]; i++) {
total += arr[i];
}
return total;
}

### Linearithmic Time: O(n log n)

// Merge Sort divides log n times and merges n times

void mergeSort(int[] arr, int l, int r) {

if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}

### Quadratic Time: O(n²)

// Print all pairs

void printPairs(int[] arr) {

for (int i = 0; i < [Link]; i++) {
for (int j = 0; j < [Link]; j++) {
[Link](arr[i] + ", " + arr[j]);
}
}
}

### Exponential Time: O(2ⁿ)

// Fibonacci (naive recursive)

int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}

### Factorial Time: O(n!)

// Generate all permutations of an array

void permute(int[] arr, int start) {

if (start == [Link]) {
// print the permutation
return;
}
for (int i = start; i < [Link]; i++) {
// swap
int temp = arr[start]; arr[start] = arr[i]; arr[i] = temp;
permute(arr, start + 1);
// swap back
temp = arr[start]; arr[start] = arr[i]; arr[i] = temp;
}
}

### O(1) – Constant Space Complexity

public int add(int a, int b) {

int sum = a + b;
return sum;
}
### O(n) – Linear Space Complexity

public int[] generateArray(int n) {

int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = i;
}
return arr;
}

### O(n^2) – Quadratic Space Complexity

public int[][] generateMatrix(int n) {

int[][] matrix = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
matrix[i][j] = i * j;
}
}
return matrix;
}

### O(log n) – Logarithmic Space Complexity (Recursive Division Example)

public void logSpaceRecursion(int n) {

if (n <= 1) return;
logSpaceRecursion(n / 2);
}

### O(n) – Space in Recursive Stack (Linear-space Recursion)

public int factorial(int n) {

if (n <= 1) return 1;
return n * factorial(n - 1);
}

Inclass Solution

// 1. Prime Security Checkpoints

import [Link];
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int start = [Link]();
int end = [Link]();
for (int i = start; i <= end; i++){
if (isPrime(i)){
[Link](i + " ");
}
}
[Link]();
}
private static boolean isPrime(int val) {
if (val == 2){
return true;
}
else if (val < 2 || val % 2 == 0){
return false;
}
for (int i = 3; i*i <= val; i = i + 2){
if (val % i == 0){
return false;
}
}
return true;
}
}

// 2. The Great Divider

import [Link];

class Main {
public static int gcd(int a, int b){
if (b == 0)
return a;
return gcd(b, a % b);
}
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int n = [Link]();
int result = [Link]();

for (int i = 1; i < n; i++){

int val = [Link]();
 result = gcd(val, result);
}
[Link](result);
}
}

// 3. Smart Grid Configuration: Identifying Valid Time Intervals

import [Link];

class Main {
private static void findfactors(int n) {
int sqrt = (int)[Link](n);
for (int i = 1; i <= sqrt; i++){
if (n % i == 0){
[Link](i + " ");
}
}
for (int i = sqrt; i >= 1; i--){
if (n % i == 0 && (n / i != i)){
[Link](n / i + " ");
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int n = [Link]();
findfactors(n);
}
}

// 4. Powering the Machine: Subarray LCM Check

import [Link];

class Main {
public static int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}

public static int lcm(int a, int b) {

 return (a / gcd(a, b)) * b;
}

public static void main(String[] args) {

Scanner sc = new Scanner([Link]);
int n = [Link](), k = [Link]();
int[] arr = new int[n];
for (int i = 0; i < n; i++){
arr[i] = [Link]();
}
int count = 0;
for (int i = 0; i < n; i++){
int lcm = arr[i];
for (int j = i; j < n - 1; j++){
if (lcm == k){
count++;
}
lcm = lcm(lcm, arr[j + 1]);
}
if (lcm == k){
count++;
}
}
[Link](count);
}
}

// 5. Odd Count Detector in a Given Range

import [Link];

class Main {
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int val1 = [Link]();
int val2 = [Link]();
int n = (val2 - val1) / 2;
n = (val1 % 2 == 0) ? n : n + 1;
[Link](n);
}
}

// 6. Trailing Zeros in Factorial Count

import [Link];
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int val = [Link](), k = 0;
while (val != 0){
val /= 5;
k += val;
}
[Link](k);
}
}

// 7. Prime Factorization of a Number

import [Link];

public class Main {

public static void primeFactors(int n) {
while (n % 2 == 0) {
[Link](2 + " ");
n /= 2;
}

for (int i = 3; i <= [Link](n); i += 2) {

while (n % i == 0) {
[Link](i + " ");
n /= i;
}
}
if (n > 2) {
[Link](n);
}
[Link]();
}

public static void main(String[] args) {

Scanner sc = new Scanner([Link]);
int num = [Link]();
primeFactors(num);
}
}

// 8. Glowing Stones: Count of Perfect Squares in a Range

import [Link];
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int i = [Link](), j = [Link](), k = 0;
while (i <= j){
if([Link](i) == [Link]([Link](i))){
k++;
}
i++;
}
[Link](k);
}
}

Postclass Solution
// 1. Minimum Deletions for Common Divisor Alignment

import [Link].*;

public class Main {

public static int gcd(int a, int b) {

return b == 0 ? a : gcd(b, a % b);
}

public static int findGCD(int[] arr) {

int result = arr[0];
for (int num : arr) {
result = gcd(result, num);
}
return result;
}

public static int minDeletionsToAlign(int[] nums, int[] numsDivide) {

[Link](nums);
int targetGCD = findGCD(numsDivide);

for (int i = 0; i < [Link]; i++) {

if (targetGCD % nums[i] == 0) {
return i;
}
}
return -1;
 }

public static void main(String[] args) {

Scanner sc = new Scanner([Link]);
int n = [Link]();
int m = [Link]();
int[] nums = new int[n];
for (int i = 0; i < n; i++)
nums[i] = [Link]();

int[] numsDivide = new int[m];

for (int i = 0; i < m; i++)
numsDivide[i] = [Link]();

int result = minDeletionsToAlign(nums, numsDivide);

[Link](result);
}
}

// 2. Jumbled Number Validator

import [Link];

class Main {
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int val = [Link]();
char[] str = [Link](val).toCharArray();
boolean isJumbled = true;

for (int i = 1; i < [Link]; i++){

int diff = [Link](str[i-1] - str[i]);
if (diff > 1){
isJumbled = false;
break;
}
}

if (isJumbled){
[Link]("Jumbled");
}
else {
[Link]("Not Jumbled");
}

}
}

String Algorithm
Inclass
1. Pattern Search in Large Text
Get a Text and pattern string from the user and write a Java program that returns all starting
indices where the pattern occurs in the text.

Example 1
Sample Input 1
ABABDABACDABABCABAB
ABABCABAB

Sample Output 1
10

Explanation
The pattern ABABCABAB starts at index 10 in the text

Solution:
import [Link];

public class Main {

static int[] findlps(String p){

char pa[] = [Link]();
int i=1, n=[Link];
int l=0;
int lps[] = new int[n];
while(i<n)
{
if(pa[i]==pa[l]){
lps[i] = l+1;
l++;
i++;
}
else{
if(l==0){
lps[i]=0;
i++;
}
else{
l = lps[l-1];
 }
}
}
return lps;
}

static boolean search(String t, String p){

int lps[] = findlps(p);
int n = [Link](), m= [Link]();
char ta[] = [Link]();
char pa[] = [Link]();
int i=0, j=0;
boolean found = false;
while(i<n && j<m){
if(ta[i]==pa[j]){
i++;
j++;
}
else if(j!=0){
j = lps[j-1];
}
else{
i++;
}
if(j==m){
[Link]((i-j)+" ");
j = lps[j-1];
found = true;
}
}
return found;
}
public static void main(String[] args) {
Scanner in = new Scanner([Link]);
String t = [Link]();
String p = [Link]();
if(!search(t,p)){
[Link]("No match found");
}
}
}
2. Text Analyzer for User Input
Find the the length of the longest substring without repeating characters.
Note: A given string containing any printable characters (letters, digits, symbols).

Example 1
Sample Input 1
abcabcbb

Sample Output 1
3

Explanation
The longest substring without repeating characters is "abc", which has a length of 3.

Solution:
import [Link];

public class Main {

static int longestSubstring(String s) {

if (s == null || [Link]() == 0) {
return 0;
}

int[] charIndex = new int[128];

int len = 0;
int left = 0;

for (int right = 0; right < [Link](); right++) {

char currentChar = [Link](right);

if (charIndex[currentChar] >= left+1) {

left = charIndex[currentChar];
}
charIndex[currentChar] = right+1;
len = [Link](len, right - left + 1);
}

return len;
}
public static void main(String[] args) {
Scanner in = new Scanner([Link]);
String s = [Link]();
[Link](longestSubstring(s));
 }
}

3. Longest Palindromic Substring Finder for Online Text Editor

Find the longest palindromic substring in the string which is get from user
Example 1
Sample Input 1
babad

Sample Output 1
bab

Explanation
The longest palindromic substring is "bab". Note that "aba" is also a valid answer, but "bab" is
returned as the answer in this case.

Solution:
import [Link];

class Main {
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
String str = [Link]();
Manacher(str);
}

private static void Manacher(String str) {

char[] str1 = [Link]();
StringBuilder t = new StringBuilder("^#");
for (char ch : str1){
[Link](ch).append("#");
}
[Link]("$");

char[] T = [Link]().toCharArray();
int[] P = new int[[Link]];
int index = 0;

int center = 0, right = 0, max = 0;

for (int i = 1; i < [Link] - 1; i++){
if (i < right){
int mirror = 2 * center - i;
P[i] = [Link](right - i, P[mirror]);
}
while (T[i + (P[i] + 1)] == T[i - (P[i] + 1)]){
P[i]++;
}
if (i + P[i] > right){
center = i;
 right = i + P[i];
}
if (max < P[i]){
max = P[i];
index = i;
}
}
int start = (index - max)/2;
[Link]([Link](start, start+max));
}
}

4. Zigzag Pattern Conversion for String Encoding

Get A string s (1 <= [Link] <= 1000) consisting of English letters (both uppercase and
lowercase) and an integer numRows (1 <= numRows <= 1000) from user and
zigzag pattern row by row, left to right based on numRows.

Example 1
Sample Input 1
PAYPALISHIRING
3

Sample Output 1
PAHNAPLSIIGYIR

Explanation
The zigzag pattern for the string "PAYPALISHIRING" with 3 rows looks like this:
P A H N
APLSIIG
Y I R
Reading the pattern line by line gives: "PAHNAPLSIIGYIR".

Solution:
import [Link];

class Main {
public static void main(String[] args) {
Scanner in = new Scanner([Link]);
String s = [Link]();
int numRows = [Link]();

[Link](convert(s, numRows));
}

public static String convert(String s, int numRows) {

if (numRows == 1) {
return s;
}

StringBuilder[] rows = new StringBuilder[numRows];

for (int i = 0; i < numRows; i++) {
rows[i] = new StringBuilder();
}

int currentRow = 0;
boolean goingDown = false;
 for (char c : [Link]()) {
rows[currentRow].append(c);

if (currentRow == 0 || currentRow == numRows - 1) {

goingDown = !goingDown;
}

if (goingDown) {
currentRow++;
} else {
currentRow--;
}
}

StringBuilder result = new StringBuilder();

for (StringBuilder row : rows) {
[Link](row);
}

return [Link]();
}
}

5. Counting Palindromic Substrings in a String

string s consisting of lowercase English letters (1 ≤ [Link] ≤ 1000). Find the number of
palindromic substrings in the string s.

Example 1
Sample Input 1
abc

Sample Output 1
3

Explanation
The palindromic substrings in "abc" are:
 "a"
 "b"
 "c"
Thus, the output is 3.

Solution:
import [Link];
public class Main {
public static int count_palin(String s) {
if (s == null || [Link]() == 0) {
return 0;
 }

int n = [Link]();
int count = 0;

for (int i = 0; i < n; i++) {

int l = i;
int r = i;
while (l >= 0 && r < n && [Link](l) == [Link](r)) {
count++;
l--;
r++;
}

l = i;
r = i + 1;
while (l >= 0 && r < n && [Link](l) == [Link](r)) {
count++;
l--;
r++;
}
}
return count;
}

public static void main(String[] args){

Scanner in = new Scanner([Link]);
String s = [Link]();
int count = count_palin(s);
[Link](count);
}
}

6. Word Ranking System for Lexicographic Dictionaries

Find the position of the give string in the dictionary if the words are allocated in
lexicographic order.

Sample Input 1
acb

Sample Output 1
2

Explanation
All permutations (sorted): abc, acb, bac, bca, cab, cba. acb is at position 2.
 Solution:
import [Link];
class Main {
public static long findRank(String str) {
int n = [Link]();
long[] fact = new long[n + 1];
fact[0] = 1;
for (int i = 1; i <= n; i++) {
fact[i] = fact[i - 1] * i;
}

long rank = 1;
for (int i = 0; i < n; i++) {
int countSmaller = 0;
for (int j = i + 1; j < n; j++) {
if ([Link](j) < [Link](i)) {
countSmaller++;
}
}
rank += countSmaller * fact[n - 1 - i];
}
return rank;
}
public static void main(String[] args){
Scanner in = new Scanner([Link]);
String s = [Link]();
long count = findRank(s);
[Link](count);
}
}

7. Secure Passphrase Validator: Check Rearrangeable Palindromes

In a password security system, a passphrase is considered strong if its characters can be
rearranged to form a palindrome (a string that reads the same backward and forward).

Example 1
Sample Input 1
ivicc

Sample Output 1
Yes

Explanation
By rearranging → civic → palindrome.

Example 2
Sample Input 2
hello

Sample Output 2
No

Explanation
No rearrangement leads to a palindrome.

Solution:
import [Link];

class main {
public static void main(String[] args) {
Scanner in = new Scanner([Link]);
String s = [Link]();

if (canRearrange(s)) {
[Link]("Yes");
} else {
[Link]("No");
}

public static boolean canRearrange(String s) {

int[] charCounts = new int[128];

for (char c : [Link]()) {

charCounts[[Link](c)]++;
}

int oddCount = 0;

for (int count : charCounts) {

if (count % 2 != 0) {
oddCount++;
}
}

return oddCount <= 1;

}
}

Postclass

1. Byteland Identity Code Verifier

The string is considered as super ascii string if characters appears in string which
frequency is equlas to its alphabetical position, where 'a' → 1, 'b' → 2, ..., 'z' → 26.
Get n inputs from user and return yes or no whether is super ascii string or not.

Sample Input 1
2
bba
scca

Sample Output 1
YES
NO

Explanation
 bba →
 'b' appears 2 times, ASCII (b) = 2
 'a' appears 1 time, ASCII (a) = 1
 Valid → YES
 scca →
 's' appears 1 time, ASCII (s) = 19 -> Not valid
 'c' appears 2 times, ASCII (c) = 3 -> Not valid
 'a' appears 1 time, ASCII (a) = 1 -> valid
 Invalid → NO

Solution:
import [Link];

class main {
public static void main(String[] args) {
Scanner in = new Scanner([Link]);
int T = [Link]();
[Link]();

for (int i = 0; i < T; i++) {

String s = [Link]();
if (isSuperAscii(s)) {
[Link]("YES");
} else {
[Link]("NO");
}
}
}

public static boolean isSuperAscii(String s) {

int[] counts = new int[26];
for (char c : [Link]()) {
counts[c - 'a']++;
}

for (int i = 0; i < 26; i++) {

 if (counts[i] > 0) {
if (counts[i] != i + 1) {
return false;
}
}
}
return true;
}
}

2. Similar Char

Tahir and Mamta are working on a project in TCS. Tahir, being a problem solver, came up
with an interesting problem for his friend Mamta.
The problem consists of a string of length N that contains only lowercase alphabets.
It is followed by Q queries.
Each query contains an integer P (1 ≤ P ≤ N), denoting a position within the string.
Mamta’s task is:
For each query, find the alphabet present at position P in the string and determine
the number of times this same alphabet appears before position P (i.e., in
positions 1 to P−1).
Mamta is busy with her office work, so she asked you to help her.

Sample Input 1
9
abacsddaa
2
9
3

Sample Output 1
3
1

Explanation
Here Q = 2 For P=9, the character at the 9th location is 'a'. The number of occurrences of
'a' before P i.e., 9 is three. Similarly, for P=3, 3rd character is 'a'. The number of
occurrences of 'a' before P. i.e., 3 is one.

Solution:
import [Link];
import [Link];
import [Link];

class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader([Link]));

int N = [Link]([Link]());
String S = [Link]();
int Q = [Link]([Link]());

int[][] prefixCount = new int[N + 1][26];

for (int i = 0; i < N; i++) {

char currentChar = [Link](i);
 int charIndex = currentChar - 'a';

for (int j = 0; j < 26; j++) {

prefixCount[i + 1][j] = prefixCount[i][j];
}
prefixCount[i + 1][charIndex]++;
}

for (int i = 0; i < Q; i++) {

int P = [Link]([Link]());
char charAtP = [Link](P - 1);
int charIndexAtP = charAtP - 'a';
int count = prefixCount[P - 1][charIndexAtP];
[Link](count);
}
}
}

3. Auto-correcting Usernames for Palindrome Checkers

Add minimum number of characters in the given string to convert it to plaindrome

Example 1
Sample Input 1
aacecaaa

Sample Output 1
aaacecaaa

Explanation
Already almost a palindrome; adding just 'a' at the front makes it fully symmetric.

Solution:
import [Link];

class Main {

public static void main(String[] args) {

Scanner sc = new Scanner([Link]);
String s = [Link]();
[Link](shortestPalindrome(s));

public static String shortestPalindrome(String s) {

if ([Link]()) {
return "";
}

String reversed = new StringBuilder(s).reverse().toString();

String combined = s + "#" + reversed;

int n = [Link]();
int[] lps = new int[n];
int length = 0;
int i = 1;
 while (i < n) {
if ([Link](i) == [Link](length)) {
length++;
lps[i] = length;
i++;
} else {
if (length != 0) {
length = lps[length - 1];
} else {
lps[i] = 0;
i++;
}
}
}

int PrefixLength = lps[n - 1];

String prefixToAdd = [Link](0, [Link]() - PrefixLength);

return prefixToAdd + s;
}
}

4. Converting Museum Artifact Numbers to Roman Numerals

Sample Input 1
3749

Sample Output 1
MMMDCCXLIX
Explanation
3749 → MMMDCCXLIX
• 3000 → MMM
• 700 → DCC
• 40 → XL
• 9 → IX

Solution:
import [Link];

class Main {

public static void main(String[] args) {

Scanner scanner = new Scanner([Link]);
int num = [Link]();
[Link](intToRoman(num));
[Link]();
}

public static String intToRoman(int num) {

int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
 String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

StringBuilder roman = new StringBuilder();

for (int i = 0; i < [Link]; i++) {

while (num >= values[i]) {
num -= values[i];
[Link](symbols[i]);
}
}

return [Link]();
}
}