Join Us
Loading Similar Posts
Entering edit mode
1. Given an integer N, the task is to count the minimum steps required to reduce the value of N to 0 by performing the following two operations:
- Consider integers A and B where N = A * B (A != 1 and B != 1), reduce N to max(A, B)
- Decrease the value of N by 1
2. Given a string S containing letter and digit and an integer K where, 
and 
. The task is to return the K-th letter of the new string S’.
The new string S’ is formed from old string S by following steps:
1. If the character read is a letter, that letter is added at end of S’.
2. If the character read is a digit, then entire string S’ repeatedly written d-1 more times in total.
Note: The new string is guaranteed to have less than 2^63 letters.
same gfg question
3. one more tough DP question
Remaining MCQs based on linux commands mostly, SQL question,OS round robin question .
Entering edit mode
#Problem 1: Minimum Steps to Reduce N to 0
from collections import deque
def min_steps_to_zero(N):
queue = deque([(N, 0)]) # (current value, steps)
visited = set()
while queue:
current, steps = queue.popleft()
if current == 0:
return steps
# Decrement operation
if current - 1 not in visited:
visited.add(current - 1)
queue.append((current - 1, steps + 1))
# Factorization operation
for i in range(2, int(current**0.5) + 1):
if current % i == 0:
A, B = i, current // i
next_n = max(A, B)
if next_n not in visited:
visited.add(next_n)
queue.append((next_n, steps + 1))
return -1 # In case no solution found
#Problem 2: K-th Character in Expanded String
def find_kth_character(S, K):
current_length = 0
stack = []
for char in S:
if char.isalpha():
current_length += 1
if current_length == K:
return char
elif char.isdigit():
digit = int(char)
if current_length * digit >= K:
# If we would surpass K, we need to find the K-th character in the expanded form
stack.append((current_length, digit))
current_length *= digit
# If we exit the loop, we haven't found it in the letters directly
return None # if K is out of bounds
