Welcome to A December of Algorithms (2021). After overwhelming responses from previous years, we present you with a new collection of algorithms to implement this December. Each Day, Each Algorithm ;) Finish them all to get a certificate :)
Send a pull request only after completing all 31 algorithms.
Please submit all PRs on or before January 10th 11:59 PM IST.
We have a small collection of algorithms, one for every day of the month. Scroll down to take a look at them. All you need to do is fork this repository, implement all 31 algorithms and send a pull request over to us. Check out our FAQ for more information.
- December 1 - Elegant facelift
- December 2 - Bingo!
- December 3 - Lotto!
- December 4 - Sandhya and her Tic-Tac-Toe love
- December 5 - Biscuit Bonanza
- December 6 - Save The Templars
- December 7 - Amy helps Pawnee
- December 8 - Anomalous Counter
- December 9 - Dream 11
- December 10 - Juicy Orange Field
- December 11 - Maze Festival
- December 12 - Ford vs Ferrari
- December 13 - Desert Shopping
- December 14 - The Math Test
- December 15 - Twinkling Bracelets
- Maintainers
- FAQ
- There is a collection of necklaces where each necklace has various stones embedded in it. Each type of stone is designated by a lowercase letter in the range ascii
[a-z]. - There may be multiple occurrences of a stone in a necklace. A stone is called a
faceliftif it occurs at least once in each of the necklaces in the collection. - Given a list of stones embedded in each of the necklaces, display the number of types of
facelift's in the collection.
Input: arr = ['abcdde', 'baccd', 'eeabg']
Output: 2
Input: arr = ['abc', 'def', 'ghi', βjklβ]
Output: 0
- In sample input 1, only
aandboccur in every necklace. Therefore, the output is2. - In sample input 2, there are no characters repeating in the list. Therefore, the output is
0.
-
Your local community conducts a game night every Saturday and they want you to lead a game of Bingo this weekend. You must come up with numbers to be read out during the game. The numbers can be chosen on the basis of certain criteria.
-
Begins with a positive integer, sum of squares of digits must replace the number. Continue until the number is 1 or loops interminably without including 1.
-
The numbers which end in 1 are to be selected. Return βYESβ if the number is selected, and βNOβ if not.
Input: n = 2
Output: NO
Input: n = 19
Output: YES
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
- In a lottery game , each participant can choose a lucky board which is in the form of a 2D
(x x y)grid. He/she can win the lottery if they are able to find their name on the lucky board. Find whether a particular participant can win the game or not. Assume that there can be more than one winner who wins the lottery. - Return true if the participant wins else return false
- The name of the participant has to be arranged in a sequentially adjacent manner.
- The neighbouring alphabets can be horizontal as well as vertical
- Same alphabet cell cannot be used more than once while forming the name.
Input: [["D","J","O","G"],["W","B","H","S"],["T","Z","N","E"]], name = "JOHN"
Output: true
Input: [["L","N","A","C"],["W","B","A","D"],["T","Z","F","E"]], name = "DEV"
Output: false
- Sandhya likes to play tic-tac-toe (using
2x2matrix), and uses the elements0and1. She is wondering how many matrices withXrows andYcolumns there are. Everyone obviously knows that - it is just2Xβ Y. But what no one knows is that, she considers two identical matrices if and only if by permuting theXno.of rows and then permuting theYno.of columns, and the resulting matrix is transverse of itself. - Help Sandhya by finding the number of
XΓYmatrices which are distinct according to her definition (even though she doesn't know how to solve them). Since the answer can/may be quite large, compute it modulo 10^9+7.
Input: 1 5
Output: 6
Input: 10 10
Output: 508361223
According to Sandhya's definition, there are 6 different binary matrices.
This is because the number of 1-s uniquely identifies a 1Γ5 matrix and
the number of 1-s can take any value between 0 and 5 inclusive.
- A local biscuit store sells only
2types of biscuits: circular and rectangular biscuits. They are referred to by the numbers0and1respectively. The customers stand in a queue and they either purchase circular or rectangular biscuits. - The number of biscuits is equal to the number of customers. They are placed in a stack.
- At each step: If the customer at the front of the queue prefers the biscuit on the top of the stack, they will take it and leave the queue.
- Otherwise, they will directly go to the queue's end.
- Consider two integer arrays
customersandbiscuitswherebiscuits[i]is the type of theith biscuit in the stack (i = 0 is the top of the stack) andcustomers[j]is the preference of thejth customer in the initial queue (j = 0 is the front of the queue). This continues until none want to take the top biscuit and are thus unable to eat. - Return the number of customers that are unable to eat.
customers = [1,1,1,0,1]
biscuits = [1,0,0,0,1,1]
Customers that are unable to eat = 3
customers = [1,1,0,0]
biscuits = [0,1,0,1]
Customers that are unable to eat = 0
customers = [1,1,0,0,1,0]
biscuits = [0,1,0,1,1,1]
Customers that are unable to eat = 1
Input: customers = [1,1,0,0], biscuits = [0,1,0,1]
Output: 0
- Front customer leaves the top sandwich and returns to the end of the line making customers = [1,0,0,1].
- Front customer leaves the top sandwich and returns to the end of the line making customers = [0,0,1,1].
- Front customer takes the top sandwich and leaves the line making customers = [0,1,1] and biscuits = [1,0,1].
- Front customer leaves the top sandwich and returns to the end of the line making customers = [1,1,0].
- Front customer takes the top sandwich and leaves the line making customers = [1,0] and biscuits = [0,1].
- Front customer leaves the top sandwich and returns to the end of the line making customers = [0,1].
- Front customer takes the top sandwich and leaves the line making customers = [1] and biscuits = [1].
- Front customer takes the top sandwich and leaves the line making customers = [] and biscuits = [].
Hence all customers are able to eat.
- The conflict continues. The Templar Assasins
Tand the UndyingUare fighting to the death, but the bad is prevailing over the good. The Templars must band together in order to combat the Undying. - At the top of the Undying Resource tower, everyone is initially arranged in a circular path.
- The Templar Assassin at index 1 is in front of the Templar Assassin at index 2 and stands close to the Templar Assassin at index
n. - The Templars must band together in order to win the battle.
- The Templars have a particular ability that allows them to switch bodies with anyone.
- Assist the Templars in determining the least number of swaps required so that they can all stand together.
- Given the sequence of Templar Assasins
Tand the UndyingU, return the minimal number of swaps required.
Input: UUTUTUT
Output: 1
Input: UTUTTU
Output: 1
To get all U and T together in the sample test case, first replace the T at index 3 with U at index 6.
Second, we can combine all U and T by swapping U at index 3 with T at index 2.
- Amy Santiago is a pilot and she went to Pawnee for official work. She noticed that the city had a food shortage due to the devastating impact of COVID-19. So, she decided to help the people who are in desperate need of food by supplying them on their building with the help of her private jet-plane.
- All the buildings are represented by three pairs of points:
(a1, b1), (a2,b2) and (a3,b3). - The jet can fly in a direction either parallel to the
xaxis or theyaxis. It drops the food packets on every building Amy flies over in her flight. - The food packet will be wasted if it is dropped on the boundary of the building as it will fall down. No two buildings touch each other. Figure out the number of buildings that receive the food packets on each flight.
- A single line integer i.e the number of buildings that received the food packets on their roofs on each flight.
Number of Buildings: 3
Coordinates of the buildings:
1 0 0 2 2 2
1 3 3 5 4 0
5 4 4 5 4 4
Number of jet-planes: 3
x = 1
x = 2
y = 1
Buildings that received food:
1
1
2
Number of Buildings: 4
Coordinates of the buildings:
1 1 2 3 4 1
2 5 3 3 0 0
3 2 2 1 1 3
4 5 5 0 1 0
Number of jet-planes: 2
x=1
y=3
Buildings that received food:
1
2
- You found a rather bizarre counter around your area. You see that there are two dials, one is the cycle dial and another is the counter value dial.
- When you start the counter, you see in the counter dial that it starts with the initial value 3 and then you see the counter value decreases by 1 each second until the value becomes 1.
- In the next second you see that the cycle dialer is incremented to 1 and the counter value becomes twice the initial value of the counter in the previous cycle.
- You decided to invite your friends to play a guessing game, i.e to find the value displayed by the counter at a particular time(in seconds).
Input: time = 22
Output: counter value = 24
Input: time = 0
Output: counter value = 0
Input: time = 22
Output: 24
time=22 marks the beginning of the fourth cycle.
So the counter value is double the number displayed at the beginning of the third cycle(when time=10): 12X2 = 24.
This is shown in the diagram in the problem statement.
- As a Cricket coach, you have to pick `P` understudies to address your school. There are `N` understudies.
- The aptitude rating of `N` understudies has been given as input, which is a positive number indicating how gifted they are. Right away, it likely will not be possible to pick a sensible gathering, so you will give a piece of the understudies one-on-one educating.
- It requires one hour of preparing to extend the ability rating of any understudy by 1. The resistance season is starting very soon, so you'd like to notice the base number of extensive stretches of guidance you need to give before you can pick a sensible gathering.
- Output the base number of long periods of instruction required, before you can pick a reasonable group of `P` understudies.
N = 4, P =3
N = [3, 1, 9, 100]
Base number of periods required = 14
N = 6, P = 2
N = [5, 5, 1, 2, 3, 4]
Base number of periods required = 0
N = 5, P = 5
N = [7, 7, 1, 7, 7]
Base number of periods required = 6
- You are in a field of juicy oranges that is like a grid of size
n x n. You plan to collect most of the oranges in the field before the storm comes. Each cell can be any one of the following:- A cell can be empty (represented by 0), so you can pass through the cell.
- A cell that contains the orange trees where you can pick up the oranges and pass through to the next cell. (represented by 1)
- A cell covered with prickles and thorns that blocks your way to the next cell (represented by -1).
- As itβs a big field you have to follow certain rules to find the maximum number of oranges you can collect before the storm hits:-
- You begin at the first cell and you have to reach the last cell by moving right or down through valid cells (cells that do not contain prickles and thorns).
- After reaching the last cell, you have to return to the first cell by moving left or up through valid cells.
- When passing through a cell containing oranges, you pick it up, and the cell becomes an empty cell.
- If there is no valid path between the first and last cell, then no oranges can be collected.
Input: field = [[0,1,-1],[1,0,-1],[1,1,1]]
Output: 5
Input: field = [[0,1,-1],[1,0,-1],[1,1,1]]
Output: 5
You started at (0, 0) and went down, down, right right to reach (2, 2).
4 oranges were picked up during this single trip, and the matrix becomes [[0,1,-1],[0,0,-1],[0,0,0]].
Then, the player went left, up, up, left to return home, picking up one more orange.
The total number of oranges picked up is 5, and this is the maximum possible.
-
On the occasion of Halloween, a grand corn maze puzzle has been set up in the fields of Hubbβs farm, New York. There are several mystery boxes hidden at each magic spot.
-
Assume that there are
Nmagic spots from1toNin the entire field. -
Given the points to the spots
PandQand the distance between themDand also a participant who choses the starting spotA, the path chosen to reach the final spotBand the final magic spotC. -
Identify whether the participant can reach the destination spot or not.
-
If yes print the minimum distance(shortest path) covered and the path taken by the participant to reach the final magic spot. Else print "NO PATH FOUNDβ.
-
Note: If a pathway connects
AtoBwith distanceDthen it means that it will connect fromBtoAwith the same distanceD.
Input:
N = 6
P Q D
1 2 2
2 5 5
2 3 4
1 4 1
4 3 3
3 5 1
A = 1, B = 3, C = 6
Output: No path found
N = 10
P Q D
1 5 78
1 8 221
2 7 92
2 8 159
3 5 55
3 6 179
3 10 237
4 8 205
5 6 191
8 10 157
A = 6, B = 3, C = 2
Output: Shortest path = 692
Path taken = 6 3 5 1 8 2
Input:
N = 10
P Q D
1 5 78
1 8 221
2 7 92
2 8 159
3 5 55
3 6 179
3 10 237
4 8 205
5 6 191
8 10 157
A = 6, B = 3, C = 2
Output: Shortest path = 692
Path taken = 6 3 5 1 8 2
- In the 2nd test case there are 10 magic spots and 10 number of pathways which connects the spots.
The next 10 lines of input contains 3 numbers representing the names of start spot,
and destination spot, distance between them
for example, for the first magic spot
- starting spot is 1
- passing through spot is 5
- distance between 1 and 5 is 78
1
/ \
4 - 8 6 - 5
/ \ \ /
2 10 - 3
/
7
- For the user's input 6, 3, 2 representing starting, passing through,destination spots respectively there exits a shortest path to reach spot 2 from spot 6 passing through spot 3.
- The minimum distance travelled is 692
- Path followed is 6->3->5->1->8->2
- Two friends Carroll Shelby and Ken Miles are playing a game where they arrange all the toy cars in a row and run them in random directions.
- Each car has a certain superiority level associated with it and both max and sergio are aware of the superiority levels. They want to know the state of cars once they move them.
- We are given an array
carsof integers representing cars in a row. For each car, the absolute value represents its superiority, and the sign represents its direction (positive meaning right, negative meaning left). - Each car moves at the same speed. Find out the state of the cars after all collisions.
- If two cars meet, the less superior one will break. If both are of the same superiority, both will break. Two cars moving in the same direction will never meet.
Input: cars = [4,8,-2]
Output: [4,8]
Input: cars = [5,-5]
Output: []
Input: cars = [10,2,-5]
Output: [10]
Input: cars = [4,8,-2]
Output: [4,8]
- The car with superiority level 8 and -2 collide resulting in car with superiority level 8.
- The cars 4 and 8 never collide because they are moving in the same direction.
- Therefore, the ouptut is [4,8]
Resources (Spoiler)
- You are a diamond merchant in Dubai. You have
xunsold diamonds, and each diamondphas a purity levelmβ, and a minimum pricenβ. - You also have
zclients, and each clientjwants a diamond with a purity greater thankβ±Όand a price less than or equal torβ±Ό. - Each client can buy at most one diamond, and each diamond can have at most one buyer. What is the maximum number of diamonds you can sell?
Input:
z = 3, x = 3
kβ = 5, rβ = 110
kβ = 9, rβ = 500
kβ = 20, rβ = 400
mβ = 10, nβ = 100
mβ = 2, nβ = 200
mβ = 30, nβ = 300
Output: Maximum number of diamonds sold = 2
Input:
z = 2, x = 2
kβ = 3, rβ = 100
kβ = 5, rβ = 150
mβ = 4, nβ = 145
mβ = 2, nβ = 80
Output: Maximum number of diamonds sold = 2
In case 1:
- Client 0 will be interested in diamond 0 because it has more than kβ = 5 units of purity and costs less than rβ = 110 .
- Both of the other diamonds are outside of this client's price range.
- Client 1 will be interested in diamonds 0 and 2 , as both these diamonds have more than kβ = 9 units of purity and cost less than rβ = 500 .
- They will not be interested in the remaining diamonds because it's less pure.
- Client 2 will be interested in diamond 2 because it has more than kβ = 20 units of purity and costs less than rβ = 400 .
- They will not be interested in the other two diamonds because they are less pure.
- All three clients are interested in the same two houses, so you can sell at most two houses in the following scenarios:
- Client 0 buys diamond 0 and client 1 buys diamond 2.
- Client 1 buys diamond 0 and client 2 buys diamond 2.
- Client 0 buys diamond 0 and client 2 buys diamond 2 .
- Thus, we print the maximum number of diamond you can sell, 2, on a new line.
- Amy has her Math exam tomorrow and she has not prepared for it.
- There are
nchapters in her book andith chapter has chaptericoncepts. She hasxhours to prepare for the exam. She decides that she can studyynumber of concepts from the chapters in each hour. - If a chapter has less than
yconcepts, then she will cover all the concepts of that chapter and take a break for the rest of the hour. - Return a minimum integer
ysuch that she covers all the chapters of her Math book withinxhours.
Input: chapter = [3,6,7,11], x = 8
Output: 4
Input: chapter = [30,11,23,4,20], x = 5
Output: 30
She can study 4 concepts from her chapters per hour such that, she can cover all the concepts from the chapters within 8 hours.
- Pinky is a college student who works for her momβs online Bracelet store and sells amazing collections of bracelets on a daily basis.
- She takes a maximum number of
ndays for the bracelets to be delivered to the customers. - The
ith customer has orderedinumber of bracelets. - She prepares the bracelets according to the order in which she received the bookings. She schedules a maximum number of bracelets to be made and delivered in a day, such that she has sufficient time to manage her college work.
- Return the least number of bracelets that can be made in a day for them to be delivered in n days.
Input: number of bracelets = [3,2,2,4,1,4], n = 3
Output: 6
Input: number of bracelets = [1,2,3,1,1], n = 4
Output: 3
Pinky can make 6 bracelets and deliver them in a day such that she delivers all the orders within 3 days.
Day 1: 3, 2
Day 2: 2, 4
Day 3: 1, 4
| Nikhilesh S | Keerthana S | Harshitha | Pranav D | Nitya Samavedam | Madhumita R | Poujhit MU | Sahari Krithik | Vishnuvasan |
|---|---|---|---|---|---|---|---|---|
 |
 |
 |
 |
 |
 |
 |
 |
 |
| π¨π§π | π | π | π | π | π | π | π | π |
Anyone who is passionate about coding and can dedicate a little time a day for the challenge for the next 31 days.
You don't need to submit it everyday. Just submit it once you're done with all 31 algorithms.
Not a problem. While coding every day is nice, we understand that other commitments might interfere with it. Plus its holiday season. So you don't have to solve one problem every day. Go at your own pace. One per day or 7 a week or even all 30 in a day.
Anything! New to GoLang? Best way to practice it. Wanna find out what all this hype about Python is? Use it! Any and all languages are welcomed. Maybe you could try using a different language for every problem as a mini-challenge?
If you are new to Git or GitHub, check out this out GitHub
Our code ninjas are hard at work preparing the rest of the problems. Don't worry, they'll be up soon.
We have a folder for each day of the month. Simply complete your code and move the file into that folder. Be sure to rename your file to the following format: language_username or language_username_problemname
Some examples:
python3_exampleUser.py
c_exampleUser.c
Please do not modify any existing files in the repository.
I forked the repository but some problems were added only after that. How do I access those problems?
Not to worry! Open your nearest terminal or command prompt and navigate over to your forked repository. Enter these commands:
git remote add upstream https://github.com/SVCE-ACM/A-December-of-Algorithms-2021.git
git fetch upstream
git merge upstream/mainIf you're curious, the commands simply add a new remote called upstream that is linked to this repository. Then it 'fetches' or retrieves the contents of the repository and attempts to merge it with your progress. Note that if you've already added the upstream repository, you don't need to re-add it in the future while fetching the newer questions.
This shouldn't happen unless you modify an existing file in the repository. There's a lot of potential troubleshooting that might be needed, but the simplest thing to do is to make a copy of your code outside the repository and then clone it once again. Now repeat the steps from the answer above. Merge it and then add your code. Now proceed as usual. :)
Open up an issue on this repository and we'll do our best to help you out.
