Count minimum steps to get the given desired array - GeeksforGeeks
Consider an array with n elements and value of all the elements is zero. We can perform following operations on the array.
Read full article from Count minimum steps to get the given desired array - GeeksforGeeks
Consider an array with n elements and value of all the elements is zero. We can perform following operations on the array.
- Incremental operations:Choose 1 element from the array and increment its value by 1.
- Doubling operation: Double the values of all the elements of array.
One important thing to note is that the task is to count the number of steps to get the given target array (not to convert zero array to target array).
The idea is to follow reverse steps, i.e. to convert target to array of zeros. Below are steps.
Take the target array first. Initialize result as 0. If all are even, divide all elements by 2 and increment result by 1. Find all odd elements, make them even by reducing them by 1. and for every reduction, increment result by 1. Finally we get all zeros in target array.
// Returns count of minimum operations to covert a
// zero array to target array with increment and
// doubling operations.
// This function computes count by doing reverse
// steps, i.e., convert target to zero array.
int
countMinOperations(unsigned
int
target[],
int
n)
{
// Initialize result (Count of minimum moves)
int
result = 0;
// Keep looping while all elements of target
// don't become 0.
while
(1)
{
// To store count of zeroes in current
// target array
int
zero_count = 0;
int
i;
// To find first odd element
for
(i=0; i<n; i++)
{
// If odd number found
if
(target[i] & 1)
break
;
// If 0, then increment zero_count
else
if
(target[i] == 0)
zero_count++;
}
// All numbers are 0
if
(zero_count == n)
return
result;
// All numbers are even
if
(i == n)
{
// Divide the whole array by 2
// and increment result
for
(
int
j=0; j<n; j++)
target[j] = target[j]/2;
result++;
}
// Make all odd numbers even by subtracting
// one and increment result.
for
(
int
j=i; j<n; j++)
{
if
(target[j] & 1)
{
target[j]--;
result++;
}
}
}
}
Read full article from Count minimum steps to get the given desired array - GeeksforGeeks