Scaler Topics Fortnightly Contest - 27 Editorial
DSA Fortnightly - 27 Editorial
This article is part of the Scaler Topics Fortnightly Contest - 27
Marble Bucket Game
Jack and his friend are playing a strategic marble game. They have a row of N buckets, and the i-th bucket contains A[i] marbles. During their turns, they can remove any number of marbles, at least 1, from the first non-empty bucket in the row. The game begins with Jack taking the first turn, followed by alternating turns between the two players.
If a player cannot remove any marbles from any non-empty bucket on their turn, they will lose the game. Both players aim to play optimally. Determine who will win: return 1 if Jack wins, and return 2 if his friend wins.
Problem Constraints
Input Format
- The first argument is an array of integers A.
Output Format
- Return an integer denoting the required answer.
Transform Your Career
Choose from our industry-leading programs designed for career success
Modern Software and AI Engineering Program
Master full-stack development with AI integration
+1000 moreModern Data Science and ML with specialisation in AI
Advanced data science techniques with AI specialization
+1000 moreAdvanced AIML with Specialisation in Agentic AI
Deep dive into AIML with focus on Agentic systems
+1000 moreDevOps, Cloud & AI Platform Engineering
Build and manage AI-powered cloud infrastructure
+1000 moreAI Engineering Advanced Certification by IIT-Roorkee
Premier AI engineering certification from IIT-Roorkee
Example
Example Input Input 1:
Input 2:
Example Output Output 1:
Output 2:
Example Explanation Explanation 1: Jack starts by removing 4 marbles from the first bucket, leaving the buckets with [1, 3, 4, 2]. His friend then takes 1 marble from the first bucket as this is the only option available, leaving [0, 3, 4, 2]. Jack proceeds by taking 2 marbles from the second bucket, making the buckets [0, 1, 4, 2]. His friend follows by removing 1 marble from the second bucket, resulting in [0, 0, 4, 2]. Jack proceeds by taking 3 marbles from the third bucket, leaving [0, 0, 1, 2]. His friend removes 1 marble from the third bucket, leaving [0, 0, 0, 2]. Finally, Jack clears all the marbles from the last bucket, leaving all buckets empty. As his friend cannot make a move with no marbles left, Jack wins.
Explanation 2: Jack starts by removing 1 marble from the first bucket as this is the only option available, resulting in [0, 1, 1, 1]. His friend then removes 1 marble from the second bucket, leaving [0, 0, 1, 1]. Jack proceeds by taking 1 marble from the third bucket, resulting in [0, 0, 0, 1]. His friend takes the last marble from the last bucket, leaving all buckets empty [0, 0, 0, 0]. With no marbles remaining and no available moves, Jack is unable to make a move and, therefore, loses the game.
Hint
- The first bucket with more than 1 marble holds the key to the game. Player can either clear it or cleverly leave just 1 to set a trap for the next turn.
- Sequentially noting initial single-marble buckets unveils strategic advantages in subsequent turns.
Complete Solution
Boys love Shoes
A number of boys are evaluating different shoe brands. Initially, all B brands are being assessed. In each round, each boy casts a vote for his favored brand among the remaining options. Subsequently, only the brands with the highest number of votes persist. The voting procedure persists until only one brand prevails. Ascertain whether the voting process can perpetually continue or if, irrespective of the boys' choices, they will eventually converge on a single brand after a finite number of rounds.
Problem Constraints
Input Format
- The first argument is integer A.
- The second argument is integer B.
Output Format
- Return 1 if in the end a single brand is present else return 0.
Example
Example Input Input 1:
Input 2:
Example Output Output 1:
Output 2:
Example Explanation Explanation 1: In the first example, there are 8 ways people could vote: [ 1| 1| 1, 1| 1| 2, 1| 2| 1, 1| 2| 2, 2| 1| 1, 2| 1| 2, 2| 2| 1, 2| 2| 2 ].
Explanation 2: Only 1 choice is there.
Hint
- What is the number of options that is present in the infinite amount of rounds?
- Choose the smallest such number of options.
- How does this number and B relate to the answer?
Scaler Placement Report and Statistics
Scaler learners achieved 2.5x salary growth with average post-Scaler CTC reaching ₹23L.
Google
Amazon
Microsoft
Flipkart
Adobe1200+ moreComplete Solution
Faulty Calculator
In a wonderland where Alice resides, she stumbled upon a peculiar calculator that operates in a unique manner compared to calculators in the real world. However, you, hailing from the real world, have been tasked with the role of Alice's instructor. This calculator exhibits a malfunction solely during subtraction operations. Instead of displaying the correct outcome of subtracting integer A from integer B, it produces an alternative result. This alternative result is determined by the number of digits that change as you increment B by 1 until it matches A. As her teacher, you provide Alice with the difference between the actual result and the erroneous result, enabling her to comprehe1<=A,B<=10^9nd the workings of the real world in a time complexity of O(logA) using algorithm.
Problem Constraints
Input Format
- The first argument is integer A.
- The second argument is integer B.
Output Format
- Return the error between actual result and faulty result given by peculiar calculator.
Example
Example Input Input 1:
Input 2:
Example Output Output 1:
Output 2:
Example Explanation Explanation 1: Alice (A-B)=8, real(A-B)=8 hence error is abs(8-8)=0
Explanation 2: Alice (A-B)=2, real(A-B)=1 hence error is abs(2-1)=1
Turn Learning into Career Growth
Hint
- Think about such a function which we can code out, dividing by 10 everytime. This way we can achieve complexity of O(log A).
Complete Solution
Spaceship on Mission
There are many planets in the universe represented as P(i, j) where (i, j) is the location of the planet. Two planets P1(i1, j1) and P2(i2, j2) are called neighbouring if |i1 - i2| + |j1 - j2| = 1.
There is a spaceship at planet P1(A[0], A[1]). The spaceship can only travel to neighbouring planets taking 1 unit of time. The spaceship has a mission to destroy the planet P2(A[2], A[3]). Once the spaceship destroys the planet P2, it creates a portal P2 and it makes the spaceship teleport to the another portal at planet P3(A[4], A[5]). The spaceship needs to return to its planet P1. The spaceship needs to complete the mission in the shortest time possible. Completion of the mission means destroying the planet P2 and coming back to the planet P1.
What is the maximum number of planets that the spaceship can visit twice while completing the mission. A is an array of size 6 which represents the location of the planets.
Problem Constraints
Input Format
- The first and only argument is array of integers A.
Output Format
- Return the maximum number of cells that both robots can traverse together if they each follow their respective shortest paths home.
Example
Example Input Input 1:
Input 2:
Example Output Output 1:
Output 2:
Example Explanation Explanation 1:
The spaceship can take the path as (3, 1), (3, 2), (3, 3), (2, 3), (1, 3). It then teleports to (6, 4). The returning path would be (6, 4), (6, 3), (5, 3), (4, 3), (3, 3), (3, 2), (3, 1). It visits the planets (3, 1), (3, 2) and (3, 3) twice. So, the answer is 3.
Explanation 2:
The path taken would be (5, 2), (4, 2), (3, 2), (2, 2). The returning path would be (7, 2), (6, 2), (5, 2). The only planet to be visited twice is (5, 2). So, the answer is 1.
Hint
- Try using geometry and maths!
- See that if a formula can be created to solve in O(1)
