Minimum steps to reach end of array under constraints - GeeksforGeeks


Minimum steps to reach end of array under constraints - GeeksforGeeks
Given an array containing one digit numbers only, assuming we are standing at first index, we need to reach to end of array using minimum number of steps where in one step, we can jump to neighbor indices or can jump to a position with same value.
In other words, if we are at index i, then in one step you can reach to, arr[i-1] or arr[i+1] or arr[K] such that arr[K] = arr[i] (value of arr[K] is same as arr[i])



Input : arr[] = {5, 4, 2, 5, 0}
Output : 2
Explanation : Total 2 step required.
We start from 5(0), in first step jump to next 5 
and in second step we move to value 0 (End of arr[]).

Input  : arr[] = [0, 1, 2, 3, 4, 5, 6, 7, 5, 4,
                 3, 6, 0, 1, 2, 3, 4, 5, 7]
Output : 5
Explanation : Total 5 step required.
0(0) -> 0(12) -> 6(11) -> 6(6) -> 7(7) ->
(18)                                                          
(inside parenthesis indices are shown)


This problem can be solved using BFS. We can consider the given array as unweighted graph where every vertex has two edges to next and previous array elements and more edges to array elements with same values. Now for fast processing of third type of edges, we keep 10 vectors which store all indices where digits 0 to 9 are present. In above example, vector corresponding to 0 will store [0, 12], 2 indices where 0 has occurred in given array.
Another Boolean array is used, so that we don’t visit same index more than once. As we are using BFS and BFS proceeds level by level, optimal minimum steps are guaranteed.
int getMinStepToReachEnd(int arr[], int N)
{
    // visit boolean array checks whether current index
    // is previously visited
    bool visit[N];
    // distance array stores distance of current
    // index from starting index
    int distance[N];
    // digit vector stores indicies where a
    // particular number resides
    vector<int> digit[10];
    //  In starting all index are unvisited
    memset(visit, false, sizeof(visit));
    //  storing indices of each number in digit vector
    for (int i = 1; i < N; i++)
        digit[arr[i]].push_back(i);
    //  for starting index distance will be zero
    distance[0] = 0;
    visit[0] = true;
    // Creating a queue and inserting index 0.
    queue<int> q;
    q.push(0);
    //  loop untill queue in not empty
    while(!q.empty())
    {
        // Get an item from queue, q.
        int idx = q.front();        q.pop();
        //  If we reached to last index break from loop
        if (idx == N-1)
            break;
        // Find value of dequeued index
        int d = arr[idx];
        // looping for all indices with value as d.
        for (int i = 0; i<digit[d].size(); i++)
        {
            int nextidx = digit[d][i];
            if (!visit[nextidx])
            {
                visit[nextidx] = true;
                q.push(nextidx);
                //  update the distance of this nextidx
                distance[nextidx] = distance[idx] + 1;
            }
        }
        // clear all indices for digit d, because all
        // of them are processed
        digit[d].clear();
        //  checking condition for previous index
        if (idx-1 >= 0 && !visit[idx - 1])
        {
            visit[idx - 1] = true;
            q.push(idx - 1);
            distance[idx - 1] = distance[idx] + 1;
        }
        //  checking condition for next index
        if (idx + 1 < N && !visit[idx + 1])
        {
            visit[idx + 1] = true;
            q.push(idx + 1);
            distance[idx + 1] = distance[idx] + 1;
        }
    }
    //  N-1th position has the final result
    return distance[N - 1];
}

http://www.geeksforgeeks.org/minimum-step-reach-one/
Given a positive number N, we need to reach to 1 in minimum number of steps where a step is defined as converting N to (N-1) or converting N to its one of the bigger divisor.
Formally, if we are at N, then in 1 step we can reach to (N – 1) or if N = u*v then we can reach to max(u, v) where u > 1 and v > 1.

We can solve this problem using breadth first search because it works level by level so we will reach to 1 in minimum number of steps where next level for N contains (N – 1) and bigger proper factors of N.
Complete BFS procedure will be as follows, First we will push N with steps 0 into the data queue then at each level we will push their next level elements with 1 step more than its previous level elements. In this way when 1 will be popped out from queue, it will contain minimum number of steps with it, which will be our final result.
In below code a queue of a structure of ‘data’ type is used which stores value and steps from N in it, another set of integer type is used to save ourselves from pushing the same element more than once which can lead to an infinite loop. So at each step, we push the value into set after pushing that into the queue so that the value won’t be visited more than once.
int minStepToReachOne(int N)
{
    queue<data> q;
    q.push(data(N, 0));
 
    // set is used to visit numbers so that they
    // won't be pushed in queue again
    set<int> st;
 
    //  loop untill we reach to 1
    while (!q.empty())
    {
        data t = q.front();     q.pop();
         
        // if current data value is 1, return its
        // steps from N
        if (t.val == 1)
            return t.steps;
 
        //  check curr - 1, only if it not visited yet
        if (st.find(t.val - 1) == st.end())
        {
            q.push(data(t.val - 1, t.steps + 1));
            st.insert(t.val - 1);
        }
 
        //  loop from 2 to sqrt(value) for its divisors
        for (int i = 2; i*i <= t.val; i++)
        {
 
            // check divisor, only if it is not visited yet
            // if i is divisor of val, then val / i will
            // be its bigger divisor
            if (t.val % i == 0 && st.find(t.val / i) == st.end())
            {
                q.push(data(t.val / i, t.steps + 1));
                st.insert(t.val / i);
            }
        }
    }
}
Read full article from Minimum steps to reach end of array under constraints - GeeksforGeeks

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts