You are currently at cell (1, 1) of an N X M grid. There is a rule that decides how you can move in the grid to reach the position (N, M). The rule is, that if you are at cell (x, y) then from there you can either move to cell (x, x+y) or to cell (x+y, y) in one step. Your task is to find the minimum number of steps that you must take to reach cell (N, M) starting from current position i.e. (1, 1) Note: If it is not possible to reach (N, M) from (1, 1), then return-1 as your output. Input Specification: input1: An integer value representing the value of N where 1<=N

You are currently at cell (1, 1) of an N X M grid. There is a rule that decides how you can move in the grid to reach the position (N, M). The rule is, that if you are at cell (x, y) then from there you can either move to cell (x, x+y) or to cell (x+y, y) in one step. Your task is to find the minimum number of steps that you must take to reach cell (N, M) starting from current position i.e. (1, 1) Note: If it is not possible to reach (N, M) from (1, 1), then return-1 as your output. Input Specification: input1: An integer value representing the value of N where 1<=N

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Q: You are playing a card game. In this game, your opponent places n monster cards onto the board, the…

A: Actually, program is an executable software that runs on a computer.

Q: Four in a row is a game in which players take turns adding tokens to the columns on the game board.…

A: +-----------------------+ | Game | +-----------------------+ | -players: List<Player>| |…

Q: Children often play a memory game in which a deck of cards containing matching pairs is used.The…

A: The objective of the question is to create a program that simulates a memory game. The game involves…

Q: There are N light bulbs numbered 1 to N, all kept off initially. There are also N persons who will…

A: In computer science, a pattern refers to a reusable solution to a commonly occurring problem. A…

Q: The figures illustrate a solution for a game played on a 4x4 board with three blue marbles, three…

A: In order to solve the Marble Game and determine the fewest number of moves, we can implement a…

Q: A deck of cards contains 52 cards with four suits: club, diamond, heart and spade ranging in values…

A: A deck of 52 cards, with four suits: club, diamond, heart and spade ranging in values from 2, … to…

Q: Can you help me trying to do this code because I am struggling big time with this. question that i…

A: A class is a blueprint used in object-oriented programming to create objects, or instances. It…

Q: Idiot’s Delight is a fairly simple game of solitaire, yet it is difficult to win. The goal is to…

A: The scope of this question is to create a Python module named "idiots_delight.py" and define several…

Question

You are currently at cell (1, 1) of an N X M grid. There is a rule that decides
how you can move in the grid to reach the position (N, M). The rule is, that if
you are at cell (x, y) then from there you can either move to cell (x, x+y) or to
cell (x+y, y) in one step.
Your task is to find the minimum number of steps that you must take to reach
cell (N, M) starting from current position i.e. (1,1)
Note: If it is not possible to reach (N, M) from (1, 1), then return -1 as your output.
Input Specification:
input1: An integer value representing the value of N where 1<=N
input2: An integer value representing the value of M where M< 106
Output Specification:
Return the minimum number of steps.
Example 1:
input1: 3
input2: 2
Output: 2

Expert Solution

This question has been solved!

Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.

This is a popular solution!

SEE SOLUTION Check out a sample Q&A here

Step 1

VIEW

Step 2

VIEW

Trending now

This is a popular solution!

Step by step

Solved in 2 steps with 1 images

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions

We have n glasses which can hold a varying amount of liquid. We will say that glass1 is size q1 quarts and glass2 is size q2 quarts, etc. We now give you a size, say x quarts. You must give me a glass of exactly x quarts. You are allowed to fill any glass to exactly its size and to pour any liquid from one glass into another. When you pour, you either have to empty the glass you are pouring from or fill the glass you are pouring into. Can you do it?More concrete example: G1 has size 10 quarts. G2 has size 4 quarts. G3 has size 1 quart. You can get a 5 quart drink by filling G1, pouring 4 quarts from it into G2 and 1 quart of it into G1. After that, G1 has exactly 5 quarts. In the same problem, we could get 8 quarts by filling G2 twice and emptying it into G1 twice. Given This: Write an algorithm to do this and determine its complexity.
You will build a simplified, one-player version of the classic board game Battleship! In this version of the game, there will be a single ship hidden in a random location on a 5 × 5 grid. The player will have 4 guesses at most to try to sink the ship. At each guess, the player names an attacking coordinate, that is (“guess row”, “guess col”). The game ends in two conditions: (1) the player is out of guesses; (2) the player hits the ship. Examples are given in Figure 1. The 5 × 5 board is shown every time the player inputs a guess entry. The ship takes only one entry of the board and it is randomly given before the player’s guesses. The player inputs guessing entries in the Python console. Entries missed the ship are replaced by “X” in the board. You must use loop in your code. Please submit your code and console screenshots to bartleby. Code contain- ing syntax error will be graded zero. Hints: 1 Create a variable board and set it equal to an empty list…
You are given a 2 by n grid, where the cell on row i column j contains a non-negative number ai,j . You can start at either cell in the lefttmost column, and your goal is to reach either cell in the rightmost column by a sequence of moves. You can move to an adjacent cell (if it exists) in each of the 4 cardinal directions (up,down, left and right). A path achieves a score equal to the sum of values in its cells. Note that a cell which is used twice in a path only counts its value once to the score of that path.Design an algorithm which runs in O(n) time and finds a path of minimum score from the leftmost column to the rightmost column.
There are four people who want to cross a rickety bridge; they all begin on the same side. You have 17 minutes to get them all across to the other side. It is night, and they have one flashlight. A maximum of two people can cross the bridge at one time. Any party that crosses, either one or two people, must have the flashlight with them. The flashlight must be walked back and forth; it cannot be thrown, for example. Person 1 takes 1 minute to cross the bridge, person 2 takes 2 minutes, person 3 takes 5 minutes, and person 4 takes 10 minutes. A pair must walk together at the rate of the slower person's pace. Write the specification of an algorithm that solves the problem.