We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. Toll Cost Digits
  5. Discussions

Toll Cost Digits

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 18 Discussions, By:

recency

Please Login in order to post a comment

  • yashparihar729
    4 months ago+ 0 comments

    Here is my solution in java, javascript, python, C, C++, Csharp HackerRank Toll Cost Digits Problem Solution

    0|
    Permalink
  • mineman1012221
    6 months ago+ 0 comments

    Here is the solution of Toll Cost Digits Click Here

    0|
    Permalink
  • bhautik4avenger4
    1 year ago+ 1 comment

    https://zeroplusfour.com/toll-cost-digits-hackerrank-solution/ Here's how I did in all languages Java 8 , C++ , C , Python 3, Python 2.

    -1|
    Permalink
  • ludovic_cleroux
    1 year ago+ 1 comment

    I have not yet found how to solve this within the time limit, but an interesting aside.

    Using DFS/BFS on a random start node, when the path reaches back to the start node, then interesting things happen.

    Any loop back to the starting node that ends with

    loop with
    - even number, will yield all possible even numbers
    - odd number (except 5) will yield all possible odd numbers
    - 5 will yield 0 and 5
    - 0 yields 0
    

    So whenever a path circles back to the START, then you can mark all abovementioned paths as already visited.

    Given START to START: [0,4]
    # means that START->START can be reached on all even numbers [0,2,4,6,8]
    
    Given START->NODE_A = [3]
    # means that NODE_A can be reached from START_NODE with a path that end with [3]
    
    # Because START can reach itself with paths ending with [0,2,4,6,8]
    # Means we can reach START->NODE_A with [3] + [0,3,4,6,8] =  [3,5,7,9,11] = [ 3,5,7,9,1]
    

    Another interesting mechanic, is that

    - count of `1` paths = count of `9` paths
    - count of `2` paths = count of `8` paths
    - count of `3` paths = count of `7` paths
    - count of `4` paths = count of `6` paths
    - count of `5` paths NOT = count of `0` paths
    

    I'm trying this out right now, but i believe that you can calculate only the distances from a single node, then be able to infer the distances between all of the other nodes.

    (A,B) = [1]
    (A,C) = [2]
    then (BC) = (AC)+(BA) = [2] + [9] = [11] = [1]
    -------
    (A,B) = [1,2]
    (A,C) = [3,4]
    then (BC) = (AC)+(BA) = [3,4] + [1,2] = [3+1,3+4,4+1,4+2] = [4,7,5,6]
    --------
    (A,A) = [0,1]
    (A,B) = [1,2]
    (A,C) = [3,4]
    (B,C) = (A,A)+(A,C)+(BA) = [0,1] + [1,2] + [3,4] = [0+1+3, 0+1+4, 0+2+3, 0+2+4, 1+1+3, 1+1+4, 1+2+3, 1+2+4]
    = [4,5,5,6,5,6,6,7] = [4,5,6,7]
    
    0|
    Permalink
  • dixitsandeep
    2 years ago+ 0 comments

    Answering discussions about looping cases such as 2-3 ; 2-3-1-2-3 ; 2-3-1-2-3-1-2-3 .

    A cost is used as ending digit only in Solution. Meaing 1, 11, 101,111,201,991 all are same for costs this problem purpose. So unless looping creates costs ending with new digits, looping does not have impact on cost. Suppose a loop is having cost 100. It's equivalent to having cost 0. It does not matter how many times you loop around, it's not going to change ending digit. A looping between nodes of an Edge will give cost of 1000, which is equivalent to 0. This loop does not impact outcome. If problem was for absolute cost, even looping would have impacted outcome very differently, leading to infinite costs. However, in current problem even infinite looping can result only in 10 types of costs.

    All pair of (2,3) have costs ending with digit 1 or digit 6, irrespective of looping.

    2-3 = 411

    2-3-1-2-3= 1476

    2-3-1-2-3-1-2-3= 2541

    2-3-1-2-3-1-2-3-1-2-3=3606

    2-3-1-2-3-1-2-3-1-2-3-1-2-3=4671

    so on...

    For a given digit you take a pair (x,y) only once. You can take (x,y) pair for all ten digits if you can show paths-costs ending at all possible digits.

    In given example pair 2-3 can be counted only for digit 1 and digit 6. Basically this loop costs 1065, which ends in digit 5. So in each second loops the cost will be 10 making total cost ending at same digit as no-loop iteration. Looping adds only one extra digit, it does not create all random possilities.

    Suppose for a given pair of (x,y) a there is a loop cost ends at 1, in that case looping will add one digit each iteration. x,y pair will have costs ending in all 10 digits.

    Suppose for a given pair of (x,y) a there is a loop cost ends at 2, in that case looping will add 5 more costs of type.

    0|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy