Smallest number after n removals after k day
Given a set containing all the natural numbers till infinity. You have k days and an array arr, on each day you remove a[i]th smallest natural number from the set, the task is to tell the smallest number in the set after k days.
Examples:
Input: N = 5, K = 1, arr[] = {1, 2, 4, 5, 6}
Output: 3Input: N = 5, K = 3, arr = {1, 3, 5, 6, 7}
Output: 9
Approach: To solve the problem follow the below idea:
Consider the scenario where numbers are arranged in increasing order on a line. Instead of deleting numbers at positions a1, a2, …, an in each operation and then checking the first number after k operations, we approach it differently. Begin with the number 1 at the front and attempt to insert zeroes right after positions a1-1, a2-2, …, an-n in each operation. The goal is to have the zeroes occupy positions a1, a2, …, an after the insertions. After k insertions, we examine the position that 1 will end up at.
If a1 is not equal to 1, the answer is 1. Otherwise, each insertion can be processed in O(1) time if we keep track of how many of a1-1, a2-2, …, an-n are before the current position x of 1. If a1-1 through ai-i are before x, then we will insert i zeroes before x.
Step-by-step approach:
- Initializes variables j (pointer for array traversal) and x (smallest number).
- Iterate for each day: Indicates the start of the loop that simulates each day’s removal operation.
- Iterate through the array elements until the condition is met (i.e, the inner loop that increments j until the condition arr[j] <= x + j is false.)
- Update the smallest number based on the current position (i.e, updates the smallest number x based on the current position of j.)
- Output the smallest number after k days
Below is the implementation of the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; using ll = long long ; int main() { // Given values ll n = 5, k = 1; vector<ll> arr = { 1, 2, 4, 5, 6 }; // Initialize pointers and the smallest number ll j = 0, x = 1; // Iterate for each day while (k--) { // Iterate through the array elements until the // condition is met while (j < n && arr[j] <= x + j) j++; // Update the smallest number based on the current // position x += j; } // Output the smallest number after k days cout << x << "\n"; return 0; } |
Java
import java.util.*; public class SmallestNumber { public static void main(String[] args) { // Given values long n = 5 , k = 1 ; List<Long> arr = Arrays.asList(1L, 2L, 4L, 5L, 6L); // Initialize pointers and the smallest number long j = 0 , x = 1 ; // Iterate for each day while (k-- > 0 ) { // Iterate through the array elements until the // condition is met while (j < n && arr.get(( int )j) <= x + j) j++; // Update the smallest number based on the // current position x += j; } // Output the smallest number after k days System.out.println(x); } } |
Python3
# Given values n = 5 k = 1 arr = [ 1 , 2 , 4 , 5 , 6 ] # Initialize pointers and the smallest number j = 0 x = 1 # Iterate for each day while k > 0 : # Iterate through the array elements until the # condition is met while j < n and arr[j] < = x + j: j + = 1 # Update the smallest number based on the current # position x + = j k - = 1 # Output the smallest number after k days print (x) |
C#
using System; using System.Collections.Generic; using System.Linq; public class SmallestNumber { public static void Main( string [] args) { // Given values long n = 5, k = 1; List< long > arr = new List< long > { 1, 2, 4, 5, 6 }; // Initialize pointers and the smallest number long j = 0, x = 1; // Iterate for each day while (k-- > 0) { // Iterate through the array elements until the // condition is met while (j < n && arr[( int )j] <= x + j) j++; // Update the smallest number based on the // current position x += j; } // Output the smallest number after k days Console.WriteLine(x); } } |
Javascript
// Javascript code for the above approach // Given values let n = 5, k = 1; let arr = [1, 2, 4, 5, 6]; // Initialize pointers and the smallest number let j = 0, x = 1; // Iterate for each day while (k > 0) { // Iterate through the array elements until the // condition is met while (j < n && arr[j] <= x + j) j++; // Update the smallest number based on the current // position x += j; k--; } // Output the smallest number after k days console.log(x); |
3
Time complexity: O(k + n).
Auxiliary Space: O(1)