We have a set of numbers from 1 to N. In one operation we are allowed to replace A and B by rounded up value of (A+B)/2. We can perform this procedure N-1 times, We will left with single number left. We have to find the smallest single number that can we can get in the end and we have to output the steps involved, that is the value of A and B used at each step.
Example :
Input : 5 Output : Smallest Possible value: 2 Step 1: 5 4 Step 2: 5 3 Step 3: 4 2 Step 4: 3 1 Explanation : Initally we have 1 2 3 4 5, We will choose 4 and 5 and replace it with ceil value of (4+5)/2 that is 5, Now we have 1 2 3 5, we will choose 5 and 3 and replace it with ceil (3+5)/2 that is 4, Now we have 1 2 4 we will replace it by (4+2)/2 that is 3 Now we have 1 3, Replace them by (1+3)/2 hence 2. Input : 4 Output : Smallest Possible value: 2 Step 1: 2 4 Step 2: 3 3 Step 3: 3 1 Explanation : Initally we have 1 2 3 4, We will choose 2 and 4 and replace it with ceil value of (4+2)/2 that is 3, Now we have 1 3 3, we will choose 3 and 3 and replace it with ceil (3+3)/2 that is 3, Now we have 1 3 we will replace it by (1+3)/2 hence 2.
The first thing to notice is the smallest possible number we can always find cannot be less than 2, Because when we add two positive numbers greater than 1 or equal to 1 and divide them by 2 they will always be greater than 1. Now we can use greedy approach to make the value equal to 2 since this is the minimum value we can find for all sets. We will always choose the two maximum numbers are perform the operations on them. We will use a while loop and we will print the values of two biggest numbers available at each step replace them by (A+B)/2.
Implementation :
// Program to replace any two number A and B between 1 to N
// by rounded up value (A+B)/2
// and find the smallest possible that will be left also
// output the steps involved.
#include <bits/stdc++.h>
using namespace std;
void findMin(int n)
{
// Creating two variables to start with
int a = n; // Current Largest element
int b = n - 1; // Second largest element
// No of instructions intialised with zero
int instructions = 0;
// For each step we will find sum of nth and n-1th
// element of current array
cout << "Smallest Possible value: "
<< "2" << endl;
// Since we know that minumum value possible is 2 so we
// will output 2 Now we will find the steps involved.
while (instructions != (n - 1)) {
cout << "Step " << instructions + 1 << ": " << a
<< " " << b << endl;
a = (a + b + 1) / 2; // Replacing A by sum of
// A and B divided by 2
b = b - 1; // Moving to the next largest value
instructions++; // Increasing the count of
// instructions used
}
}
int main()
{
int n = 5;
findMin(n);
}
# Program to replace any two number A and B between 1 to N
# by rounded up value (A+B)/2
# and find the smallest possible that will be left also
# output the steps involved.
def findMin(n):
# Creating two variables to start with
a = n # Current Largest element
b = n - 1 # Second largest element
instructions = 0 # No of instructions
# For each step we will find sum of nth and n-1th
# element of current array
print('Smallest Possible value: 2')
# Since we know that minumum value possible is 2 so we
# will output 2 Now we will find the steps involved.
while(instructions != (n-1)):
print("Step "+str(instructions+1)+": "+str(a)+" "+str(b))
a = (a + b + 1)//2 # Replacing A by sum of A and B divided by 2
b = b - 1 # Moving to the next largest value
instructions = instructions+1 # Increasing count of instructions used
# Driver code
if __name__ == '__main__':
n = 5
findMin(n)
import java.io.*;
class Main {
// Function to find the smallest number
// and print the steps involved.
static void findMin(int n)
{
// Creating two variables to start with
int a = n; // Current Largest element
int b = n - 1; // Second largest element
// No of instructions intialised with zero
int instructions = 0;
// For each step we will find sum of nth and n-1th
// element of current array
System.out.println("Smallest Possible value: 2");
// Since we know that minumum value possible is 2 so
// we will output 2 Now we will find the steps
// involved.
while (instructions != (n - 1)) {
System.out.println("Step " + (instructions + 1)
+ ": " + a + " " + b);
a = (a + b + 1) / 2; // Replacing A by sum of
// A and B divided by 2
b = b - 1; // Moving to the next largest value
instructions++; // Increasing the count of
// instructions used
}
}
// Driver code
public static void main(String[] args)
{
int n = 5;
findMin(n);
}
}
Since we are running the loop n-1 times so time complexity will roughly be O(n)
Time Complexity: O(n)
