A bit flip of a number x is choosing a bit in the binary representation of x and flipping it from either 0 to 1 or 1 to 0.
x = 7, the binary representation is 111 and we may choose any bit (including any leading zeros not shown) and flip it. We can flip the first bit from the right to get 110, flip the second bit from the right to get 101, flip the fifth bit from the right (a leading zero) to get 10111, etc.Given two integers start and goal, return the minimum number of bit flips to convert start to goal.
Example 1:
Input: start = 10, goal = 7 Output: 3 Explanation: The binary representation of 10 and 7 are 1010 and 0111 respectively. We can convert 10 to 7 in 3 steps: - Flip the first bit from the right: 1010 -> 1011. - Flip the third bit from the right: 1011 -> 1111. - Flip the fourth bit from the right: 1111 -> 0111. It can be shown we cannot convert 10 to 7 in less than 3 steps. Hence, we return 3.
Example 2:
Input: start = 3, goal = 4 Output: 3 Explanation: The binary representation of 3 and 4 are 011 and 100 respectively. We can convert 3 to 4 in 3 steps: - Flip the first bit from the right: 011 -> 010. - Flip the second bit from the right: 010 -> 000. - Flip the third bit from the right: 000 -> 100. It can be shown we cannot convert 3 to 4 in less than 3 steps. Hence, we return 3.
Constraints:
0 <= start, goal <= 109program main
implicit none
integer :: start, goal, result
! Example 1
start = 10
goal = 7
write (*, '(A, I0, A, I0, A, I0)') 'Start: ', start, &
' Goal: ', goal, &
' Result: ', min_bit_flips(start, goal)
! Example 2
start = 3
goal = 4
write (*, '(A, I0, A, I0, A, I0)') 'Start: ', start, &
' Goal: ', goal, &
' Result: ', min_bit_flips(start, goal)
contains
function min_bit_flips(start, goal) result(result)
implicit none
integer, intent(in) :: start, goal
integer :: i, j, k, n, m, result
logical :: found
! Initialize variables
i = 0
j = 0
k = 0
n = 0
m = 0
found = .false.
! Loop until we find the minimum number of bit flips
do while (.not. found)
! Increment i
i = i + 1
! Check if we have reached the end of the binary representation of start
if (i > size(start)) then
! Reset i
i = 0
! Increment j
j = j + 1
! Check if we have reached the end of the binary representation of goal
if (j > size(goal)) then
! Reset j
j = 0
! Increment k
k = k + 1
! Check if we have reached the end of the binary representation of start
if (k > size(start)) then
! Reset k
k = 0
! Increment n
n = n + 1
! Check if we have reached the end of the binary representation of goal
if (n > size(goal)) then
! Reset n
n = 0
! Increment m
m = m + 1
! Check if we have reached the end of the binary representation of start
if (m > size(start)) then
! Reset m
m = 0
! Set found to true
found = .true.
! Break out of loop
exit
end if
end if
end if
end if
end if
! Check if the current bit is different between start and goal
if (btest(start, i) /= btest(goal, j)) then
! Increment result
result = result + 1
end if
end do
end function min_bit_flips
end program maintemp.f95:42:25:
42 | if (i > size(start)) then
| 1
Error: ‘array’ argument of ‘size’ intrinsic at (1) must be an array
temp.f95:50:29:
50 | if (j > size(goal)) then
| 1
Error: ‘array’ argument of ‘size’ intrinsic at (1) must be an array
temp.f95:58:33:
58 | if (k > size(start)) then
| 1
Error: ‘array’ argument of ‘size’ intrinsic at (1) must be an array
temp.f95:66:37:
66 | if (n > size(goal)) then
| 1
Error: ‘array’ argument of ‘size’ intrinsic at (1) must be an array
temp.f95:74:41:
74 | if (m > size(start)) then
| 1
Error: ‘array’ argument of ‘size’ intrinsic at (1) must be an array
temp.f95:90:16:
90 | if (btest(start, i) /= btest(goal, j)) then
| 1
Error: Logicals at (1) must be compared with .neqv. instead of /=
! Declare variables
integer :: start, goal, min_flips, i, j, temp
logical :: found
! Initialize variables
start = 10
goal = 7
min_flips = 0
found = .false.
! Check if start and goal are equal
if (start == goal) then
write (*,*) "No flips required"
return
endif
! Check if start and goal have the same number of bits
if (count_bits(start) /= count_bits(goal)) then
write (*,*) "Invalid input"
return
endif
! Loop through all possible bit flips
do i = 1, count_bits(start)
! Flip the bit at position i
temp = flip_bit(start, i)
! Check if the flipped number is equal to goal
if (temp == goal) then
! Increment the number of flips
min_flips = min_flips + 1
! Set found to true
found = .true.
! Break the loop
exit
endif
enddo
! Check if a flip was found
if (found) then
write (*,*) "Minimum flips: ", min_flips
else
write (*,*) "No solution found"
endif
! Function to count the number of bits in a number
function count_bits(n) result(count)
integer :: n, count
! Initialize variables
count = 0
! Loop through all bits
do while (n > 0)
! Increment the count
count = count + 1
! Shift the number to the right
n = n / 2
enddo
end function count_bits
! Function to flip a bit at a given position
function flip_bit(n, pos) result(flipped)
integer :: n, pos, flipped
! Initialize variables
flipped = n
! Shift the number to the left
flipped = flipped * 2
! Flip the bit at position pos
if (mod(n, 2) == 0) then
flipped = flipped - 1
else
flipped = flipped + 1
endif
! Shift the number to the right
flipped = flipped / 2
end function flip_bit
! Main program
program main
! Declare variables
integer :: start, goal
! Read input from the user
write (*,*) "Enter start and goal:"
read (*,*) start, goal
! Call the function to solve the problem
call solve(start, goal)
end program main
temp.f95:49:1:
49 | function count_bits(n) result(count)
| 1
Error: Unclassifiable statement at (1)
temp.f95:50:23:
50 | integer :: n, count
| 1
Error: Unexpected data declaration statement at (1)
temp.f95:63:3:
63 | end function count_bits
| 1
Error: Expecting END PROGRAM statement at (1)
temp.f95:67:30:
67 | integer :: n, pos, flipped
| 1
Error: Unexpected data declaration statement at (1)
temp.f95:84:3:
84 | end function flip_bit
| 1
Error: Expecting END PROGRAM statement at (1)
temp.f95:87:12:
87 | program main
| 1
Error: Unexpected PROGRAM statement at (1)
temp.f95:89:20:
89 | integer :: start, goal
| 1
Error: Symbol ‘start’ at (1) already has basic type of INTEGER
temp.f95:97:16:
97 | end program main
| 1
Error: Syntax error in END PROGRAM statement at (1)
f951: Error: Unexpected end of file in ‘temp.f95’
None
None
#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <queue>
std::vector<std::string> makeableRecipes(std::vector<std::string>& recipes, std::vector<std::vector<std::string>>& ingredients, std::vector<std::string>& supplies) {
std::unordered_map<std::string, std::unordered_set<std::string>> dependentRecipes;
std::unordered_set<std::string> availableSupplies(supplies.begin(), supplies.end());
for (size_t i = 0; i < recipes.size(); ++i) {
dependentRecipes[recipes[i]] = std::unordered_set<std::string>(ingredients[i].begin(), ingredients[i].end());
}
std::queue<std::string> q;
for (const auto& supply : availableSupplies) {
q.push(supply);
}
while (!q.empty()) {
const std::string currentItem = q.front();
q.pop();
for (const auto& recipe : dependentRecipes) {
if (recipe.second.count(currentItem)) {
recipe.second.erase(currentItem);
if (recipe.second.empty()) {
availableSupplies.insert(recipe.first);
q.push(recipe.first);
}
}
}
}
std::vector<std::string> result;
for (const auto& recipe : recipes) {
if (availableSupplies.count(recipe)) {
result.push_back(recipe);
}
}
return result;
}
None