Question Number 1

Language C | C++ | Java | Python

Topic Arrays

Subtopic Arrays

Type Coding

Question Maximum size square sub-matrix with all 1s

Given a binary matrix, find out the maximum size square sub-matrix with
all 1s.

Solution #include<stdio.h>
#define bool int
#define R 6
#define C 5

void printMaxSubSquare (bool M[R][C])

{
int i, j;
int S[R][C];
int max_of_s, max_i, max_j;

/* Set first column of S[][]*/

for (i = 0; i < R; i++)
S[i][0] = M[i][0];

/* Set first row of S[][]*/

for (j = 0; j < C; j++)
S[0][j] = M[0][j];

/* Construct other entries of S[][]*/

for (i = 1; i < R; i++)
{
for (j = 1; j < C; j++)
{
if (M[i][j] == 1)
S[i][j] = min (S[i][j - 1], S[i - 1][j], S[i - 1][j -
1]) + 1;
else
S[i][j] = 0;
}
}

/* Find the maximum entry, and indexes of maximum entry

in S[][] */
max_of_s = S[0][0];
max_i = 0;
max_j = 0;
for (i = 0; i < R; i++)
 {
for (j = 0; j < C; j++)
{
if (max_of_s < S[i][j])
{
max_of_s = S[i][j];
max_i = i;
max_j = j;
}
}
}

printf ("Maximum size sub-matrix is: \n");

for (i = max_i; i > max_i - max_of_s; i--)
{
for (j = max_j; j > max_j - max_of_s; j--)
{
printf ("%d ", M[i][j]);
}
printf ("\n");
}
}

/* UTILITY FUNCTIONS */
/* Function to get minimum of three values */
int min (int a, int b, int c)
{
int m = a;
if (m > b)
m = b;
if (m > c)
m = c;
return m;
}

/* Driver function to test above functions */

int main ()
{
bool M[R][C] = { {0, 1, 1, 0, 1},
{1, 1, 0, 1, 0},
{0, 1, 1, 1, 0},
{1, 1, 1, 1, 0},
{1, 1, 1, 1, 1},
{0, 0, 0, 0, 0}
};

printMaxSubSquare (M);
getchar ();
}

Input 1 { {0, 1, 1, 0, 1},

{1, 1, 0, 1, 0},
{0, 1, 1, 1, 0},
{1, 1, 1, 1, 0},
{1, 1, 1, 1, 1},
 {0, 0, 0, 0, 0}
}

Output 1 1 1 1
1 1 1
1 1 1

Difficulty Hard

Explanation
Question Number 2

Language C | C++ | Java | Python

Topic Arrays

Subtopic Arrays

Type Coding

Question
1, 2, 1, 3, 2, 5, 3, 7, 5, 11, 8, 13, 13, 17, ……..
This series is a mixture of 2 series – all the odd terms in this series form a

Fibonacci series and all the even terms are the prime numbers in ascending

order.

Write a program to find the Nth term in this series.

● The value N is a Positive integer that should be read from STDIN.

● The Nth term that is calculated by the program should be written to
STDOUT.
● Other than the value of Nth term, no other characters/strings or
message should be written to STDOUT.

Solution def fibbo(n):

n1, n2 = 0, 1
count = 0
if n <= 0:
print("Please enter a positive integer")
elif n == 1:
print(n1)
else:
while count < n:
nth = n1 + n2
n1 = n2
n2 = nth
count += 1
print(n1)

def prime(n):
count = 0
for i in range(2, 99999):
flag=0
for j in range(2,i):
if (i % j == 0):
 flag=1
break
if flag == 0:
count+=1
if count == n:
print(i)
break

# main
n = int(input())
if n%2 == 1:
fibbo(n//2+1)
else:
prime(n//2)

Input 1 14

Output 1 17

Difficulty Medium

Explanation When N = 14, the 14th term in the series is 17. So only the value 17 should be
printed
Question Number 1

Language C | C++ | Java | Python

Topic Arrays

Subtopic Arrays

Type Coding

Question Selection sorting is a simple sorting algorithm. This sorting algorithm is an in-

place comparison-based algorithm in which the list is divided into two parts,

the sorted part at the left end and the unsorted part at the right end. Initially,

the sorted part is empty and the unsorted part is the entire list.

The smallest element is selected from the unsorted array and swapped with

the leftmost element, and that element becomes a part of the sorted array.

This process continues moving unsorted array boundary by one element to

the right.

This algorithm is not suitable for large data sets as its average and worst

case complexities are of Ο(n2), where n is the number of items.’

Consider the following depicted array as an example.

For the first position in the sorted list, the whole list is scanned sequentially.

The first position where 14 is stored presently, we search the whole list and
find that 10 is the lowest value.

10 is placed at 0th index of array, and we increase the value of loop by +1.

Starting from 1st position of array, we selected 33 as minimum element

initially.

Then we found out that 14 is 2nd lowest element after searching the whole
array starting from 1st position of length-1 position

After two iterations, two least values are positioned at the

beginning in a sorted manner.

The same process is applied to the rest of the items in the array.

Following is a pictorial depiction of the entire sorting process −

Solution N = int(input()) # 5
A = [int(value) for value in
input().split(' ', N)]
#[64, 25, 12, 22, 11]

# Traverse through all array elements

 for i in range(len(A)):

# Find the minimum element in remaining

# unsorted array
min_idx = i
for j in range(i+1, len(A)):
if A[min_idx] > A[j]:
min_idx = j

# Swap the found minimum element with

# the first element
A[i], A[min_idx] = A[min_idx], A[i]

# Driver code to test above

for i in range(len(A)):
print('%d' %A[i], end=' ')

Input 1 5
64 25 12 22 11

Output 1 11 12 22 25 64

Difficulty Medium

Explanation
Question Number 2

Language C | C++ | Java | Python

Topic Arrays

Subtopic Arrays

Type Coding

Question Count number of occurrences (or frequency) in a sorted array

Given a sorted array arr[] of N integers and a number x, write a function

that counts the occurrences of x in arr[].

The expected time complexity is O(Logn)

Solution def countOccurrences(arr, n, element):

res = 0
for i in range(n):
if element == arr[i]:
res += 1
return res

# Driver code
N = int(input())
arr = [int(value) for value in
input().split(' ', N)]
#arr = [1, 2, 2, 2, 2, 3, 4, 7 ,8 ,8]
x = int(input())
print (countOccurrences(arr, N, x))

Input 1 5
12223
2

Output 1 3

Difficulty Medium

Explanation
Question Number 1

Language C | C++ | Java | Python

Topic Strings

Subtopic String sub sequence

Type Coding

Question
Longest Common Subsequence –
Let us discuss the Longest Common Subsequence (LCS) problem as

one more example problem that can be solved using Dynamic

Programming.

LCS Problem Statement: Given two sequences, find the length of

the longest subsequence present in both of them. A subsequence is

a sequence that appears in the same relative order, but not

necessarily contiguous. For example, “abc”, “abg”, “bdf”, “aeg”,

‘”acefg”, .. etc are subsequences of “abcdefg”. So a string of length n

has 2^n different possible subsequences.

It is a classic computer science problem, the basis of diff(a file

comparison program that outputs the differences between two

files), and has applications in bioinformatics.

Solution def lcs(X, Y, m, n):

if m == 0 or n == 0:
return 0
elif X[m-1] == Y[n-1]:
return 1 + lcs(X, Y, m-1, n-1)
else:
return max(lcs(X, Y, m, n-1),
lcs(X, Y, m-1, n));
 # Driver program to test the above
function
X = input()
Y = input()
print(lcs(X , Y, len(X), len(Y)))
Input 1 ABCDGH
AEDFHR

Output 1 3

Difficulty Hard

Explanation
Question Number 2

Language C | C++ | Java | Python

Topic Strings

Subtopic Strings

Type Coding

Question Given a string as an input. We need to write a program that will print all non-
empty substrings of that given string.

Solution def subString(Str, n):

# take starting point
for Len in range(1, n + 1):

# Pick ending point

for i in range(n - Len + 1):

# Print characters from current

# starting point to ending
point
j = i + Len - 1

for k in range(i, j + 1):

print(Str[k], end='')
print()

# Driver program to test above function

str1 = input()
subString(str1, len(str1))

Input 1 ABC

Output 1 A
B
C
 AB
BC
ABC

Difficulty Medium

Explanation
Question Number 1

Language C | C++ | Java | Python

Topic Arrays

Subtopic Arrays

Type Coding

Question Given an array which may contain duplicates, print all elements and their
frequencies.

Solution
#include <stdio.h>

int main()
{
int arr[100], freq[100];
int size, i, j, count;

/* Input size of array */

printf(“Enter size of array: “);
scanf(“%d”, &size);

/* Input elements in array */

printf(“Enter elements in array: “);
for(i=0; i<size; i++)
{
scanf(“%d”, &arr[i]);

/* Initially initialize frequencies to -1 */

freq[i] = –1;
}

for(i=0; i<size; i++)

{
count = 1;
for(j=i+1; j<size; j++)
{
/* If duplicate element is found */
if(arr[i]==arr[j])
{
count++;
/* Make sure not to count frequency of
same element again */
freq[j] = 0;
}
}
/* If frequency of current element is not counted
*/
 if(freq[i] != 0)
{
freq[i] = count;
}
}

/*
* Print frequency of each element
*/
printf(“\nFrequency of all elements of array : \n“);
for(i=0; i<size; i++)
{
if(freq[i] != 0)
{
printf(“%d occurs %d times\n“, arr[i],
freq[i]);
}
}
return 0;
}

Input 1 10, 20, 20, 10, 10, 20, 5, 20

Output 1 10 3
20 4
51

Input 2 10, 20, 20

Output 2 10 1
20 2

Difficulty Medium

Explanation Counting frequencies of array elements

Given an array which may contain duplicates, print all elements and their
frequencies.
Question Number 2

Language C | C++ | Java | Python

Topic Control statements

Subtopic Control statements

Type Coding

Question A Pythagorean triplet is a set of three integers a, b and c such that a 2 + b2 =

c2. Given a limit, generate all Pythagorean Triples with values smaller than
the given limit.

Solution #include <bits/stdc++.h>

// Function to generate pythagorean

// triplets smaller than limit
void pythagoreanTriplets (int limit)
{
// triplet: a^2 + b^2 = c^2
int a, b, c = 0;

// loop from 2 to max_limitit

int m = 2;

// Limiting c would limit

// all a, b and c
while (c < limit)
{

// now loop on j from 1 to i-1

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

// Evaluate and print triplets using

// the relation between a, b and c
a = m * m – n * n;
b = 2 * m * n;
c = m * m + n * n;
if (c > limit)
break;
printf (“%d %d %d\n“, a, b, c);
}
m++;
}
}
 // Driver Code
int main ()
{
int limit = 20;
pythagoreanTriplets (limit);
return 0;
}

Input 1 20

Output 1 3 4 5
8 6 10
5 12 13
15 8 17
12 16 20

Difficulty Hard

Explanation A Simple Solution is to generate these triplets smaller than the given limit

using three nested loops. For every triplet, check if the Pythagorean

condition is true, if true, then print the triplet. Time complexity of this

solution is O(limit3) where ‘limit’ is given limit.

An Efficient Solution can print all triplets in O(k) time where k is the

number of triplets printed. The idea is to use square sum relation of

Pythagorean triplet, i.e., addition of squares of a and b is equal to square of

c, we can write these number in terms of m and n such that,

a = m2 - n2
b=2*m*n
c = m2 + n2
because,
a2 = m4 + n4 – 2 * m2 * n2
b2 = 4 * m2 * n2
c2 = m4 + n4 + 2* m2 * n2

We can see that a2 + b2 = c2, so instead of iterating for a, b and c we can

iterate for m and n and can generate these triplets.

Question Number 1

Language C | C++ | Java | Python

Topic Control Statements

Subtopic Control Statements, Prime number, Functions

Type Coding

Question Sum of prime numbers in a given range

Given a range [l, r], the task is to find the sum of all the prime numbers

within that range.

Solution from math import sqrt

def checkPrime(numberToCheck) :
if numberToCheck == 1 :
return False
for i in range(2,
int(sqrt(numberToCheck)) + 1) :
if numberToCheck % i == 0 :
return False
return True

def primeSum(l, r) :
sum = 0
for i in range(r, (l - 1), -1) :
isPrime = checkPrime(i)
if (isPrime) :
sum += i
return sum

if __name__ == '__main__' :
l, r = (int(value) for value in
input().split())
 print(primeSum(l, r))

Input 1 16

Output 1 10

Input 2 4 13

Output 2 36

Difficulty Medium

Explanation Sum of prime numbers in the range of 4 and 13.

5 + 7 + 11 + 13 = 36
Question Number 2

Language C | C++ | Java | Python

Topic Array

Subtopic Arrays and subarrays

Type Coding

Question Your birthday is coming soon and one of your friends, Alex, is thinking about a

gift for you. He knows that you really like integer arrays with interesting

properties.

He selected two numbers, N and K and decided to write down on paper all

integer arrays of length K (in form a[1], a[2], …, a[K]), where every number a[i] is

in range from 1 to N, and, moreover, a[i+1] is divisible by a[i] (where 1 < i <= K),

and give you this paper as a birthday present.

Alex is very patient, so he managed to do this. Now you’re wondering, how

many different arrays are written down on this paper?

Since the answer can be really large, print it modulo 10000.

Solution def counter(n, k):
num = 0
if k == 1:
return n
else:
for i in range(1, n + 1):
for j in range(1, n + 1):
if j % i == 0:
num += 1
return num

def count(n, k):

if k == 1:
return n
if k == 2:
return counter(n, k)
mid = k // 2
x = count(n, k - mid)
y = counter(n, mid)
return x + y - 1

n = int(input())
k = int(input())
print(count(n, k))

Input 1 2
1

Output 1 2

Input 2 3
2

Output 2 5
Difficulty Medium

Explanation All possible arrays are [1, 1], [1, 2], [1, 3], [2, 2], [3, 3].