Given two positive integers N and K, and an integer X ( initially 1 ), the task is to find the minimum value of X that can be obtained after performing one of the following operations N numbers of times:
- Increment the value of X by K.
- Double the current value of X.
Examples:
Input: N = 4, K = 3, X = 1
Output: 10
Explanation:
Following operations are performed:
Operation 1: Double the value of X from 1 to 2.
Operation 2: Double the value of X from 2 to 4.
Operation 3: Add the value K(= 3) to X modifies the value from 4 to 7.
Operation 4: Add the value K(= 3) to X modifies the value from 7 to 10.
After performing the above operations N(= 4) number of times, the value of X is 10, which is minimum among all possible combinations of operations performed.Input: N = 7, K = 4, X = 1
Output: 24
Approach: The given problem can be solved by using the Greedy Approach. The idea is to perform one of the given operations repeatedly until performing the second operation locally maximize the value of X. Follow the steps below to solve the problem:
- Iterate over the range [1, N] and perform the following steps:
- If the value of X is less than K then update the value of X to X*2.
- Otherwise, increment the value of X by K.
- After completing the above steps, print the value of X as the minimum possible value of X.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum value// of X after increment X by K or twice// value of X in each of N operationsint minPossibleValue(int N, int K, int X){ // Iterate over the range [1, N] for (int i = 1; i <= N; i++) { // If the value of X is less // than equal to K if (X <= K) { X = X * 2; } // Otherwise else { X = X + K; } } // Return the minimum value of X return X;}// Driver Codeint main(){ int N = 7, K = 4, X = 1; cout << minPossibleValue(N, K, X); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG{ // Function to find the minimum value// of X after increment X by K or twice// value of X in each of N operationspublic static int minPossibleValue(int N, int K, int X){ // Iterate over the range [1, N] for(int i = 1; i <= N; i++) { // If the value of X is less // than equal to K if (X <= K) { X = X * 2; } // Otherwise else { X = X + K; } } // Return the minimum value of X return X;}// Driver Codepublic static void main(String[] args){ int N = 7, K = 4, X = 1; System.out.println(minPossibleValue(N, K, X));}}// This code is contributed by Potta Lokesh |
Python3
# Python program for the above approach# Function to find the minimum value# of X after increment X by K or twice# value of X in each of N operationsdef minPossibleValue(N, K, X): # Iterate over the range [1, N] for i in range(1, N + 1): # If the value of X is less # than equal to K if (X <= K): X = X * 2; # Otherwise else : X = X + K; # Return the minimum value of X return X;# Driver CodeN = 7;K = 4;X = 1;print(minPossibleValue(N, K, X));# This code is contributed by _saurabh_jaiswal |
C#
// C# program for the above approachusing System;class GFG { // Function to find the minimum value // of X after increment X by K or twice // value of X in each of N operations static int minPossibleValue(int N, int K, int X) { // Iterate over the range [1, N] for (int i = 1; i <= N; i++) { // If the value of X is less // than equal to K if (X <= K) { X = X * 2; } // Otherwise else { X = X + K; } } // Return the minimum value of X return X; } // Driver Code public static void Main() { int N = 7, K = 4, X = 1; Console.WriteLine(minPossibleValue(N, K, X)); }}// This code is contributed by subham348. |
Javascript
<script>// JavaScript program for the above approach// Function to find the minimum value// of X after increment X by K or twice// value of X in each of N operationsfunction minPossibleValue(N, K, X){ // Iterate over the range [1, N] for(let i = 1; i <= N; i++) { // If the value of X is less // than equal to K if (X <= K) { X = X * 2; } // Otherwise else { X = X + K; } } // Return the minimum value of X return X;}// Driver Codelet N = 7, K = 4, X = 1;document.write(minPossibleValue(N, K, X));// This code is contributed by Potta Lokesh</script> |
24
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!