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. All Contests
  2. ProjectEuler+
  3. Project Euler #79: Passcode derivation
  4. Discussions

Project Euler #79: Passcode derivation

Problem
Submissions
Leaderboard
Discussions

Sort 9 Discussions, By:

recency

Please Login in order to post a comment

  • benj_tordjman
    3 years ago+ 0 comments

    I solved this problem using mathematica and graph theory, too bad I can't use it here..

    0|
    Permalink
  • Crafter_Artisan
    5 years ago+ 0 comments

    My code is not pretty, but it worked, and despite being O(v^3) where v is the number of distinct characters in the logins, it's fast --- all testcases run in 0.05 s or less.

    0|
    Permalink
  • ErikTillema
    5 years ago+ 3 comments

    Solved this problem in O(T log T). For those seeking hints: one can look at this problem as being a graph problem, in which each letter is a Node and "letter X has to occur before letter Y in the passcode" is a directed edge from X to Y. You can then repeatedly take the lexicographically smallest letter with in-degree zero (this will be the next letter in the passcode) and remove it from the graph. If there is no letter with in-degree zero, then something is wrong. By using the right data structures, you can do this in O(E log E) where E is the number of edges in the graph.

    Let me know if you solved this problem in a completely different way, I'm curious!

    6|
    Permalink
  • steer_p1ke
    6 years ago+ 1 comment

    *I have written this code for the original project euler and it worked perfectly to find the passcode there. I tweaked it alittle for validation and something really went awfully wrong. Though, it works well for the sample testcases, original problem, only some testcases are passed. What's wrong in this code? *

    import java.io.; import java.util.; import java.text.; import java.math.; import java.util.regex.*;

    public class Solution {

    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        int size =  in.nextInt();
        String temp[] = new String[size];
        for(int i = 0; i < size; i++){
            temp[i] = in.next();
        }
        boolean flag = false;
        StringBuffer tempPassWord = new StringBuffer(temp[0]);
        for (int countLogs = 1; countLogs < temp.length && !flag; countLogs++) {
            for (int count = 2; count >= 0; count--) {
                if (!(tempPassWord + "").contains(temp[countLogs].charAt(count) + "") && count == 2) {
                    tempPassWord = tempPassWord.append(temp[countLogs].charAt(count) + "");
                } else if (!(tempPassWord + "").contains(temp[countLogs].charAt(count) + "")) {
                    tempPassWord = tempPassWord.insert(tempPassWord.indexOf(temp[countLogs].charAt(count + 1) + ""),
                            temp[countLogs].charAt(count));
                }
            }
            char tempChar;
            for (int count = 0; count < 2; count++) {
                if (tempPassWord.indexOf(temp[countLogs].charAt(count) + "") > tempPassWord
                        .indexOf(String.valueOf(temp[countLogs].charAt(count + 1)))) {
                    int index1 = tempPassWord.indexOf(String.valueOf(temp[countLogs].charAt(count)));
                    int index2 = tempPassWord.indexOf(String.valueOf(temp[countLogs].charAt(count + 1)));
                    tempChar = temp[countLogs].charAt(count);
                    tempPassWord.replace(index1, index1 + 1, String.valueOf(temp[countLogs].charAt(count + 1)));
                    tempPassWord.replace(index2, index2 + 1, tempChar + "");
                }
            }
            for(int validateCount = 0; validateCount < countLogs; validateCount++){
                for (int count = 0; count < 2; count++) {
                    if (tempPassWord.indexOf(temp[validateCount].charAt(count) + "") > tempPassWord
                        .indexOf(String.valueOf(temp[validateCount].charAt(count + 1)))) {
                        flag = true;
                        break;
                    }
                }
            }
        }
        if(flag){
            System.out.println("SMTH WRONG");
        }
        else{
          System.out.println(tempPassWord);
        }
    }
    

    }

    -2|
    Permalink
  • nickytobal
    6 years ago+ 1 comment

    in the sample 1, why TSMHWRONG is not a possible password? Given that input, how do you know that T comes after SM?

    1|
    Permalink
Load more conversations

Need Help?


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