Problem A 3 x 3 magic square is a 3 x 3 grid filled with distinct numbers from 1 to 9 such that each row, column, and both diagonals all have the same sum. Given a row x col grid of integers, how many 3 x 3 contiguous magic square subgrids are there? Note: while a magic square can only contain numbers from 1 to 9, grid may contain numbers up to 15. ...
Problem There are n friends that are playing a game. The friends are sitting in a circle and are numbered from 1 to n in clockwise order. More formally, moving clockwise from the ith friend brings you to the (i+1)th friend for 1 <= i < n, and moving clockwise from the nth friend brings you to the 1st friend. The rules of the game are as follows: ...
Problem There are numBottles water bottles that are initially full of water. You can exchange numExchange empty water bottles from the market with one full water bottle. The operation of drinking a full water bottle turns it into an empty bottle. Given the two integers numBottles and numExchange, return the maximum number of water bottles you can drink. Examples Example 1: Input: numBottles = 9, numExchange = 3 Output: 13 Explanation: You can exchange 3 empty bottles to get 1 full water bottle. Number of water bottles you can drink: 9 + 3 + 1 = 13. ...
Problem Given integers N and X, write a function that returns the number of times X appears as a value in an N by N multiplication table. Suppose you have a multiplication table that is N by N. That is, a 2D array where the value at the i-th row and j-th column is (i + 1) * (j + 1) (if 0-indexed) or i * j (if 1-indexed). ...
Problem A number is considered perfect if its digits sum up to exactly 10. Given a positive integer n, return the n-th perfect number. Examples Example 1: Input: n = 1 Output: 19 Example 2: Input: n = 2 Output: 28 Solution Method 1 - Brute Force Keep on generating the numbers with sum of digits as 10, and when count is n, return the number. ...
Problem Given a non-negative integer c, decide whether there’re two integers a and b such that a^2 + b^2 = c. Examples Example 1: Input: c = 5 Output: true Explanation: 1 * 1 + 2 * 2 = 5 Example 2: Input: c = 3 Output: false ...
Problem Given two parameters n and k and returns the value of Binomial Coefficient C(n, k). Definition Binomial coefficients, denoted by C(n, k), have two common interpretations: the coefficient of X^k in the expansion of (1 + X)^n. For eg., in (1 + X)^3, C(3, 2) gives you the coefficient of the term X^2. Expanding the expression, we see 3X^2, and indeed, C(3, 2) is equal to 3. the number of ways to choose k objects from a set of n, regardless of order. Formula $$ C(n, k) \text{ OR } \binom{n}{k} = \frac{n!}{k! * (n - k)!} $$ ...
Problem Write a method to shuffle a deck of cards. It must be a perfect shuffle – in other words, each 52! permutations of the deck has to be equally likely. Assume that you are given a random number generator which is perfect. OR How can you shuffle an array in O(n) time and O(1) space? For example, if input is an array of (1, 2, 3, 4, 5), one of the output can be (5, 4, 3, 2, 1) or (4, 2, 3, 1, 5). ...
Problem Given an integer n, return the least number of perfect square numbers that sum to n. A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not. Examples Example 1: Input: n = 12 Output: 3 Explanation: 12 = 4 + 4 + 4. ...
Problem Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal’s triangle. In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown: ...