search
HomeBackend DevelopmentC++C program to find the minimum number of hops to reach the end

C program to find the minimum number of hops to reach the end

Aug 26, 2023 am 11:41 AM
c programLook forMinimum hop count

C program to find the minimum number of hops to reach the end

Given an array of non-negative integers, representing the maximum number Steps that can be taken forward from this element. The pointer is initially located at the first index [0 index] of the array. Your goal is to reach the end The index into the array in the minimum number of steps. if unreachable end of the array, then print the largest integer.

The naive approach is to start with the initial {main} component and recursively call all components accessible from the first element. The minimum jump range from the first to the end is calculated using the minimum jump range required to reach the end from the first accessible element.

minJumps(start, end) = Min ( minJumps(k, end) )
for all k accessible from the start

Here, we will use the top-down dynamic programming approach. We will use a Hashmap to store subproblem results and whenever we create a solution, first check if the subproblem has been solved and if so use it.

Input: { 1, 2, 4, 1, 2, 2, 1, 1, 3, 8 }
Output: Minimum number of steps = 6 {1-->2-->4-->1-->3-->8}

Explanation

The first element is 1, so it can only go to 2. The second element is 2, so you can go up to 2 steps, e.g. to 4 or 1. from reach 1 to 4, and So on and so forth.

Complexity of dynamic programming methods for finding minimum numbers The number of jumps to reach the end of the array is O(n^2), and the space complexity is O(n)

Example

Real-time demonstration

#include<stdio.h>
#include<limits.h>
int min_steps (int arr[], int n){
   int steps[n];
   int i, j;
   if (n == 0 || arr[0] == 0)
      return INT_MAX;
   steps[0] = 0;
   for (i = 1; i < n; i++){
      steps[i] = INT_MAX;
      for (j = 0; j < i; j++){
         if (i <= j + arr[j] && steps[j] != INT_MAX){
            steps[i] = (steps[i] < (steps[j] + 1)) ? steps[i] : steps[j] + 1;
            break;
         }
      }
   }
   return steps[n - 1];
}
int main (){
   int arr[100];
   int n;
   printf ("Enter size of the array:");
   scanf ("%d", &n);
   printf ("Enter elements in the array:");
   for (int i = 0; i < n; i++){
      scanf ("%d", &arr[i]);
   }
   printf ("Minimum number of steps : %d", min_steps (arr, n));
   return 0;
}

Output

Enter size of array : 7
Enter elements in the array :2 1 1 5 2 1 1
Minimum number of steps : 3

The above is the detailed content of C program to find the minimum number of hops to reach the end. For more information, please follow other related articles on the PHP Chinese website!

Statement
This article is reproduced at:tutorialspoint. If there is any infringement, please contact admin@php.cn delete
C   Interview Questions and Answers: Ace Your Next Technical AssessmentC Interview Questions and Answers: Ace Your Next Technical AssessmentApr 28, 2025 am 12:10 AM

C In interviews, smart pointers are the key tools that help manage memory and reduce memory leaks. 1) std::unique_ptr provides exclusive ownership to ensure that resources are automatically released. 2) std::shared_ptr is used for shared ownership and is suitable for multi-reference scenarios. 3) std::weak_ptr can avoid circular references and ensure secure resource management.

The Future of C  : Adaptations and InnovationsThe Future of C : Adaptations and InnovationsApr 27, 2025 am 12:25 AM

The future of C will focus on parallel computing, security, modularization and AI/machine learning: 1) Parallel computing will be enhanced through features such as coroutines; 2) Security will be improved through stricter type checking and memory management mechanisms; 3) Modulation will simplify code organization and compilation; 4) AI and machine learning will prompt C to adapt to new needs, such as numerical computing and GPU programming support.

The Longevity of C  : Examining Its Current StatusThe Longevity of C : Examining Its Current StatusApr 26, 2025 am 12:02 AM

C is still important in modern programming because of its efficient, flexible and powerful nature. 1)C supports object-oriented programming, suitable for system programming, game development and embedded systems. 2) Polymorphism is the highlight of C, allowing the call to derived class methods through base class pointers or references to enhance the flexibility and scalability of the code.

C# vs. C   Performance: Benchmarking and ConsiderationsC# vs. C Performance: Benchmarking and ConsiderationsApr 25, 2025 am 12:25 AM

The performance differences between C# and C are mainly reflected in execution speed and resource management: 1) C usually performs better in numerical calculations and string operations because it is closer to hardware and has no additional overhead such as garbage collection; 2) C# is more concise in multi-threaded programming, but its performance is slightly inferior to C; 3) Which language to choose should be determined based on project requirements and team technology stack.

C  : Is It Dying or Simply Evolving?C : Is It Dying or Simply Evolving?Apr 24, 2025 am 12:13 AM

C isnotdying;it'sevolving.1)C remainsrelevantduetoitsversatilityandefficiencyinperformance-criticalapplications.2)Thelanguageiscontinuouslyupdated,withC 20introducingfeatureslikemodulesandcoroutinestoimproveusabilityandperformance.3)Despitechallen

C   in the Modern World: Applications and IndustriesC in the Modern World: Applications and IndustriesApr 23, 2025 am 12:10 AM

C is widely used and important in the modern world. 1) In game development, C is widely used for its high performance and polymorphism, such as UnrealEngine and Unity. 2) In financial trading systems, C's low latency and high throughput make it the first choice, suitable for high-frequency trading and real-time data analysis.

C   XML Libraries: Comparing and Contrasting OptionsC XML Libraries: Comparing and Contrasting OptionsApr 22, 2025 am 12:05 AM

There are four commonly used XML libraries in C: TinyXML-2, PugiXML, Xerces-C, and RapidXML. 1.TinyXML-2 is suitable for environments with limited resources, lightweight but limited functions. 2. PugiXML is fast and supports XPath query, suitable for complex XML structures. 3.Xerces-C is powerful, supports DOM and SAX resolution, and is suitable for complex processing. 4. RapidXML focuses on performance and parses extremely fast, but does not support XPath queries.

C   and XML: Exploring the Relationship and SupportC and XML: Exploring the Relationship and SupportApr 21, 2025 am 12:02 AM

C interacts with XML through third-party libraries (such as TinyXML, Pugixml, Xerces-C). 1) Use the library to parse XML files and convert them into C-processable data structures. 2) When generating XML, convert the C data structure to XML format. 3) In practical applications, XML is often used for configuration files and data exchange to improve development efficiency.

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

Safe Exam Browser

Safe Exam Browser

Safe Exam Browser is a secure browser environment for taking online exams securely. This software turns any computer into a secure workstation. It controls access to any utility and prevents students from using unauthorized resources.

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

mPDF

mPDF

mPDF is a PHP library that can generate PDF files from UTF-8 encoded HTML. The original author, Ian Back, wrote mPDF to output PDF files "on the fly" from his website and handle different languages. It is slower than original scripts like HTML2FPDF and produces larger files when using Unicode fonts, but supports CSS styles etc. and has a lot of enhancements. Supports almost all languages, including RTL (Arabic and Hebrew) and CJK (Chinese, Japanese and Korean). Supports nested block-level elements (such as P, DIV),

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Atom editor mac version download

Atom editor mac version download

The most popular open source editor