Minimum operation required to make N as sum of distinct powers of X
Given an integer N and a base X, the task is to find the minimum number of operations required to represent N as a sum of the distinct powers of X. In each operation, you can either increment or decrement N. You are allowed to make the given operation any number of times
Examples:
Input: N = 7, X = 3
Output: 3
Explanation: It will be optimal to increment N by 3 in 3 operations. Then, N = 10 = 30 + 33.Input: N = 53, X = 7
Output: 3
Explanation: It can be verified that it will be optimal to decrement N by 3 using operation 3 times. Then, N = 50 = 70 + 72.
Approach: Implement the idea below to solve the problem
The problem is simple Greedy Logic based. The key observation is we have to find the sum of two distinct powers, Which is nearest to the N. After finding such a pair of powers of X, Just output the absolute difference between sum of powers and N.
Steps were taken to solve the problem:
- Create an ArrayList let’s say list for storing all powers of X till less than 105.
- Initialize a variable let’s say min for storing a minimum number of operations required.
- Run two nested loops for i = 0 to i < list.size() and j = 0 to j < list.size() and follow below mentioned steps under the scope of the loop:
- If (i == j), then continue;
- Else, get some of the different powers at index i and j in the list and update min, If the absolute difference between sum and N is less than the previously stored value in the min variable.
- Return the value of min.
Below is the code to implement the approach:
Java
// Java code to implement the approach
import java.io.*;
import java.lang.*;
import java.util.*;
class Main {
public static void main(String[] args)
throws java.lang.Exception
{
int N = 6;
int X = 2;
// Function call
System.out.println(MinOperations(N, X));
}
// Method for returning minimum
// MinOperations
static int MinOperations(int N, int X)
{
// ArrayList to store the powers
// less than or equal to 10^5
// for any X
ArrayList<Integer> list = new ArrayList<>();
// Power Counter
int counter = 0;
// Variable for storing minimum
// operations
int min = Integer.MAX_VALUE;
// While Loop for initializing
// list of powers
while ((int)(Math.pow(X, counter))
<= (int)Math.pow(10, 5)) {
list.add((int)(Math.pow(X, counter)));
counter++;
}
// Nested loops to traverse list
// So we can find nearest sum
// of distinct powers of X
for (int i = 0; i < list.size(); i++) {
for (int j = 0; j < list.size(); j++) {
if (i == j)
continue;
else {
// Variable to hold
// sum of different
// powers
int sum = list.get(i) + list.get(j);
// If it is nearest to
// N, then update min
min = abs(sum - N) < min ? abs(sum - N)
: min;
}
}
}
System.out.println(list);
// Returning the minimum number
// of operations required
return (min);
}
// Method for returning
// absolute values
static int abs(int a) { return a < 0 ? -a : a; }
}
Time Complexity: O(17*17) ~ O(1), As the Maximum length of the list can be at most 17, Then the total number of loops will iterate 17*17 times.
Auxiliary Space: O(17) ~ O(1), As the Maximum length of the list can be 17, Which is for X = 2.
Given an integer N and a base X, the task is to find the minimum number of operations required to represent N as a sum of the distinct powers of X. In each operation, you can either increment or decrement N. You are allowed to make the given operation any number of times
Examples:
Input: N = 7, X = 3
Output: 3
Explanation: It will be optimal to increment N by 3 in 3 operations. Then, N = 10 = 30 + 33.Input: N = 53, X = 7
Output: 3
Explanation: It can be verified that it will be optimal to decrement N by 3 using operation 3 times. Then, N = 50 = 70 + 72.
Approach: Implement the idea below to solve the problem
The problem is simple Greedy Logic based. The key observation is we have to find the sum of two distinct powers, Which is nearest to the N. After finding such a pair of powers of X, Just output the absolute difference between sum of powers and N.
Steps were taken to solve the problem:
- Create an ArrayList let’s say list for storing all powers of X till less than 105.
- Initialize a variable let’s say min for storing a minimum number of operations required.
- Run two nested loops for i = 0 to i < list.size() and j = 0 to j < list.size() and follow below mentioned steps under the scope of the loop:
- If (i == j), then continue;
- Else, get some of the different powers at index i and j in the list and update min, If the absolute difference between sum and N is less than the previously stored value in the min variable.
- Return the value of min.
Below is the code to implement the approach:
Java
// Java code to implement the approach
import java.io.*;
import java.lang.*;
import java.util.*;
class Main {
public static void main(String[] args)
throws java.lang.Exception
{
int N = 6;
int X = 2;
// Function call
System.out.println(MinOperations(N, X));
}
// Method for returning minimum
// MinOperations
static int MinOperations(int N, int X)
{
// ArrayList to store the powers
// less than or equal to 10^5
// for any X
ArrayList<Integer> list = new ArrayList<>();
// Power Counter
int counter = 0;
// Variable for storing minimum
// operations
int min = Integer.MAX_VALUE;
// While Loop for initializing
// list of powers
while ((int)(Math.pow(X, counter))
<= (int)Math.pow(10, 5)) {
list.add((int)(Math.pow(X, counter)));
counter++;
}
// Nested loops to traverse list
// So we can find nearest sum
// of distinct powers of X
for (int i = 0; i < list.size(); i++) {
for (int j = 0; j < list.size(); j++) {
if (i == j)
continue;
else {
// Variable to hold
// sum of different
// powers
int sum = list.get(i) + list.get(j);
// If it is nearest to
// N, then update min
min = abs(sum - N) < min ? abs(sum - N)
: min;
}
}
}
System.out.println(list);
// Returning the minimum number
// of operations required
return (min);
}
// Method for returning
// absolute values
static int abs(int a) { return a < 0 ? -a : a; }
}
Time Complexity: O(17*17) ~ O(1), As the Maximum length of the list can be at most 17, Then the total number of loops will iterate 17*17 times.
Auxiliary Space: O(17) ~ O(1), As the Maximum length of the list can be 17, Which is for X = 2.
Denial of responsibility! Techno Blender is an automatic aggregator of the all world’s media. In each content, the hyperlink to the primary source is specified. All trademarks belong to their rightful owners, all materials to their authors. If you are the owner of the content and do not want us to publish your materials, please contact us by email – [email protected]. The content will be deleted within 24 hours.