Back to Subject

Unit 2: Basic math operations (addition, subtraction, multiplication, division and exponentiation) - Practice Quiz

CSE329 — Prelude To Competitive Coding 60 Questions
0 Correct 0 Wrong 60 Left
0/60

1 What does modular exponentiation compute?

Modular Exponentiation Easy
A.
B.
C.
D.

2 What is the time complexity of computing using exponentiation by squaring?

Exponential squaring Easy
A.
B.
C.
D.

3 In exponentiation by squaring, when the exponent is even, equals:

Exponential squaring Easy
A.
B.
C.
D.

4 Fast modulo multiplication is mainly used to:

Fast modulo multiplication Easy
A. Divide two numbers exactly
B. Find the square root of a number
C. Sort an array of numbers
D. Multiply two large numbers modulo while avoiding overflow

5 Which technique does fast modulo multiplication resemble in its approach?

Fast modulo multiplication Easy
A. Bubble sort
B. Binary search
C. Repeated doubling and addition
D. Prime factorization

6 Which of the following is a non-square number?

N-th non-square number Easy
A.
B.
C.
D.

7 What is the 1st non-square number (starting counting from 1)?

N-th non-square number Easy
A.
B.
C.
D.

8 The modular multiplicative inverse of modulo is a number such that:

Modular multiplicative inverse Easy
A.
B.
C.
D.

9 A modular multiplicative inverse of modulo exists if and only if:

Modular multiplicative inverse Easy
A. is even
B. is prime always
C.
D.

10 What is the modular multiplicative inverse of modulo ?

Modular multiplicative inverse Easy
A.
B.
C.
D.

11 Which property is used in modular exponentiation to keep intermediate values small?

Modular Exponentiation Easy
A.
B.
C.
D.

12 Compute .

Modular Exponentiation Easy
A.
B.
C.
D.

13 For an matrix where is odd, the middle row index (0-based) is:

Sum of middle row and element in matrix Easy
A.
B.
C. (integer division)
D.

14 In a matrix, the middle element is located at position:

Sum of middle row and element in matrix Easy
A.
B.
C.
D.

15 A row is a circular rotation of another if it can be obtained by:

Checking if all rows of a matrix are circular rotations of each other Easy
A. Shifting elements cyclically
B. Reversing the elements
C. Removing duplicate elements
D. Sorting the elements

16 A common technique to check if one string is a rotation of another is to check if it is a substring of:

Checking if all rows of a matrix are circular rotations of each other Easy
A. The sorted first string
B. The first string concatenated with itself
C. The reversed first string
D. An empty string

17 For two sets and , equals:

Inclusion - Exclusion Principle Easy
A.
B.
C.
D.

18 If , , and , then is:

Inclusion - Exclusion Principle Easy
A.
B.
C.
D.

19 The pigeonhole principle states that if items are placed into containers with , then:

Pigeonhole principle Easy
A. At least one container holds more than one item
B. Every container holds exactly one item
C. No container holds any item
D. All containers are empty

20 If 13 people are in a room, by the pigeonhole principle at least two share the same:

Pigeonhole principle Easy
A. First name
B. Exact birthday
C. Birth month
D. Height

21 Fast modulo multiplication (also called Russian peasant multiplication under a modulus) computes without overflow by repeatedly doubling and adding. What is the primary advantage of this technique over directly computing first?

Fast modulo multiplication Medium
A. It always runs in time
B. It removes the need for a modulus entirely
C. It produces a different mathematical result than direct multiplication
D. It avoids overflow when exceeds the data type's range

22 Using the doubling method to compute , the loop processes the bits of . What is the final result?

Fast modulo multiplication Medium
A.
B.
C.
D.

23 Exponentiation by squaring computes in multiplications. Which recurrence correctly describes it for even ?

Exponential squaring Medium
A.
B.
C.
D.

24 How many multiplications does exponentiation by squaring perform (approximately) to compute ?

Exponential squaring Medium
A.
B.
C.
D.

25 The -th non-square (non-perfect-square) number is given by the formula . What is the th non-square number?

N-th non-square number Medium
A.
B.
C.
D.

26 Using the formula , what is the th non-square number?

N-th non-square number Medium
A.
B.
C.
D.

27 What is using modular exponentiation?

Modular Exponentiation Medium
A.
B.
C.
D.

28 In modular exponentiation computing , why is the result reduced modulo after every multiplication rather than only at the end?

Modular Exponentiation Medium
A. To change the final answer
B. To make the exponent smaller each step
C. To keep intermediate values small and prevent overflow
D. Because the modulus must be prime

29 What is the time complexity of computing using fast modular exponentiation?

Modular Exponentiation Medium
A.
B.
C.
D.

30 The modular multiplicative inverse of modulo exists if and only if which condition holds?

Modular multiplicative inverse Medium
A. is prime
B.
C. is even
D.

31 What is the modular multiplicative inverse of modulo ?

Modular multiplicative inverse Medium
A.
B.
C.
D.

32 When is prime, Fermat's Little Theorem gives the modular inverse of as which expression?

Modular multiplicative inverse Medium
A.
B.
C.
D.

33 For an odd-sized matrix, the middle element lies at which index (0-based)?

Sum of middle row and element in matrix Medium
A.
B. using integer division
C.
D.

34 Given the matrix , what is the sum of the middle row?

Sum of middle row and element in matrix Medium
A.
B.
C.
D.

35 A common technique to check whether every row of a matrix is a circular rotation of the first row uses string concatenation. If the first row (as a string) is , a row is a circular rotation of it when:

Checking if all rows of a matrix are circular rotations of each other Medium
A. is a substring of
B. equals the reverse of
C. is a substring of
D. has the same length as only

36 Consider a matrix with rows , , and . Are all rows circular rotations of the first row?

Checking if all rows of a matrix are circular rotations of each other Medium
A. No, none are rotations
B. Yes, each is a rotation of
C. No, only the second row is a rotation
D. Yes, but only if reversed

37 How many integers from to are divisible by or ?

Inclusion - Exclusion Principle Medium
A.
B.
C.
D.

38 For three finite sets, the inclusion-exclusion principle gives as:

Inclusion - Exclusion Principle Medium
A.
B.
C.
D.

39 If people are in a room, the pigeonhole principle guarantees that at least how many share the same birth month?

Pigeonhole principle Medium
A.
B.
C.
D.

40 What is the minimum number of items needed so that, when placed into boxes, at least one box contains at least items?

Pigeonhole principle Medium
A.
B.
C.
D.

41 You need to compute where can each be up to . Direct multiplication overflows 64-bit integers. Which technique correctly computes this without overflow using only integer arithmetic?

Fast modulo multiplication Hard
A. Computing and first, then multiplying directly
B. Right-shifting the product by 32 bits before taking modulo
C. Binary (Russian peasant) multiplication adding to a running result modulo while doubling
D. Using

42 How many modular multiplications (including squarings) does exponentiation by squaring perform in the worst case to compute , where has bits?

Exponential squaring Hard
A. Approximately multiplications
B. Exactly multiplications
C. Approximately multiplications
D. Approximately multiplications

43 The -th non-square (non-perfect-square) positive integer is given by the closed form . What is the -th non-square number?

N-th non-square number Hard
A.
B.
C.
D.

44 Using Fermat's little theorem, what is ?

Modular Exponentiation Hard
A.
B.
C.
D.

45 The modular inverse of modulo exists if and only if which condition holds?

Modular multiplicative inverse Hard
A.
B. is prime
C.
D. is even and is odd

46 Compute the modular multiplicative inverse of modulo .

Modular multiplicative inverse Hard
A.
B.
C.
D.

47 To compute inverses of modulo a prime in time, the recurrence is used. This works because implies which congruence?

Modular multiplicative inverse Hard
A.
B.
C.
D.

48 To compute for prime using modular exponentiation, which exponent should be used?

Modular Exponentiation Hard
A.
B.
C.
D.

49 How many integers in are divisible by at least one of , , or ?

Inclusion - Exclusion Principle Hard
A.
B.
C.
D.

50 How many integers in are divisible by none of , , or ?

Inclusion - Exclusion Principle Hard
A.
B.
C.
D.

51 From any set of integers chosen from , the pigeonhole principle guarantees that at least one pair satisfies which relationship?

Pigeonhole principle Hard
A. Their sum equals
B. Their difference is exactly
C. Both are prime numbers
D. One number divides the other

52 In any sequence of distinct real numbers, the Erdős–Szekeres theorem (a pigeonhole application) guarantees a monotonic subsequence of length at least:

Pigeonhole principle Hard
A.
B.
C.
D.

53 For an matrix with odd , the sum of the middle row and middle column shares which element that must be counted only once to avoid double counting?

Sum of middle row and element in matrix Hard
A. The top-left corner element
B. No element is shared between them
C. The central element at index using integer division
D. The last element

54 Given a matrix where element (0-indexed), what is the sum of the middle row?

Sum of middle row and element in matrix Hard
A.
B.
C.
D.

55 To check whether all rows of an matrix are circular rotations of the first row, the standard efficient approach concatenates the first row with itself and then does what?

Checking if all rows of a matrix are circular rotations of each other Hard
A. Searches each subsequent row as a substring using KMP in per row
B. Computes the sum of each row and compares totals
C. Sorts each row and compares element sets
D. Reverses each row and checks for equality

56 Consider rows and . Why is a valid circular rotation of ?

Checking if all rows of a matrix are circular rotations of each other Hard
A. appears as a substring of
B. and have equal sums so rotation is guaranteed
C. is the reverse of
D. is a sorted permutation of

57 When computing with a very large exponent given as a decimal string, and prime with , the exponent can first be reduced modulo which value?

Modular Exponentiation Hard
A.
B.
C.
D.

58 Exponentiation by squaring can be generalized to compute the -th power of an matrix. What is its time complexity for computing ?

Exponential squaring Hard
A.
B.
C.
D.

59 Given any integers, the pigeonhole principle guarantees a non-empty subset whose sum is divisible by . Which quantities serve as the pigeons and holes in the standard proof?

Pigeonhole principle Hard
A. Prefix sums modulo are the pigeons; the residue classes are the holes
B. The integers themselves are pigeons; their values are holes
C. The divisors of are pigeons; the multiples are holes
D. Pairwise sums are pigeons; even/odd parity are holes

60 Why does the formula for the -th non-square number add rather than simply ?

N-th non-square number Hard
A. Because floor of is undefined for large
B. To ensure the result is always even
C. To correctly account for perfect squares that fall within the range as grows, rounding to the nearest integer
D. Because is always irrational for non-squares
Previous MCQ
Unit 1
Next MCQ
Unit 3