Question Number

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.
Question Number

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])
Question Number

{
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 ();
}
Question Number

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.
Question Number 2

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

Language

C | C++ | Java | Python

Topic

Arrays

Subtopic Arrays

Type

Coding
Question Number

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
Question Number

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.
Question Number

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

Following is a pictorial depiction of the entire sorting process −

Question Number

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
Question Number

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

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.
Question Number

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
Question Number 2

Output 1 A
B
C
AB
BC
ABC

Difficulty Medium

Explanation
Question Number

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.
Question Number

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)
{
Question Number

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
Question Number

Output 2

10 1
20 2

Difficulty Medium

Counting frequencies of array elements

Given an array which may contain duplicates, print all elements and their frequencies.
Explanation
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 a2 + b2 = c2. Given a limit,
generate all Pythagorean Triples with values smaller than the given limit.
Question Number 2

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
Question Number 2

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

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.
Question Number

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
Question Number

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.

Question Number 2

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
Question Number 2

Output 2 5

Difficulty Medium

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