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.
  1. Prepare
  2. Algorithms
  3. Greedy
  4. Sherlock and The Beast
  5. Discussions

Sherlock and The Beast

Sort by

recency

|

534 Discussions

|

  • alban_tyrex
     + 0 comments

    Here is my c++ solution, you can have the implementation link here : https://youtu.be/R01NQ4Zt2qA

    void decentNumber(int n) {
    int three = ((3 - (n % 3)) % 3 ) * 5;
    if(three > n) cout << -1;
    else cout << string(n - three, '5') << string(three, '3');
    cout << endl;
}

  • purple6
     + 0 comments

    python

    def decomposeNumberBy3and5(n):
    """If possible, get {3: a, 5: b}, such that n = a*3 + b*5.
    3 has the priority."""
    if n in (1, 2, 4, 7):
        return None

    match n % 3:
        case 0:
            return {3: n // 3, 5: 0}
        case 1:
            return {3: n // 3 - 3, 5: 2}  # 1 = 5 * 2 - 3 * 3
        case 2:
            return {3: n // 3 - 1, 5: 1}  # 2 = 5 * 1 - 3 * 1


def decentNumber(n):
    if (decomp := decomposeNumberBy3and5(n)) is None:
        print(-1)
    else:
        print("5" * decomp[3]*3 + "3" * decomp[5]*5)

  • shashvat_gupta
     + 0 comments
    public static void decentNumber(int n) {
        String result = "-1";
        
        if(n%3 == 0) {
            result = "5".repeat(n);
        } else {
            for(int i = 5; i <= n; i+=5) {
                if((n-i)%3 == 0) {
                    result = "5".repeat(n-i) + "3".repeat(i);
                    break;
                }
            }
        }
      System.out.println(result);
    }

  • jmcparland
     + 0 comments

    Haskell

    module Main where

import Control.Monad (replicateM_)

solve :: String -> String
solve nstr = do
    let n = read nstr :: Int
    let res = n `divMod` 3
    case go res of
        Nothing -> "-1"
        Just (q, r) -> replicate (q * 3) '5' ++ replicate r '3'
  where
    go :: (Int, Int) -> Maybe (Int, Int)
    go (q, r)
        | q < 0 = Nothing
        | r `mod` 5 == 0 = Just (q, r)
        | otherwise = go (q - 1, r + 3)

main :: IO ()
main = do
    cases <- readLn :: IO Int
    replicateM_ cases $ do
        n <- getLine
        putStrLn $ solve n

  • klimber_mail
     + 0 comments

    While not the optimal, I was happy with this one in Java:

        public static void decentNumber(int n) {
        // Decent number s of length n, can be represented as
        // x = Number of sets of 5
        // y = Number of Sets of 3
        //  (3*x) + (5*y) = n;
        // Isolating x
        // x = (n - (5*y)) / 3
        // Need to solve for lowest integer y > 0 than gives integer x > 0
        
        for(int y = 0; y < n; y++){
            if((n - (5 * y)) % 3 == 0) {
                int x = (n - (5 * y)) / 3;
                if (x < 0) {
                    break;
                }
                String decentForLength = "5".repeat(x * 3) + "3".repeat(y * 5);
                System.out.println(decentForLength);
                return;
            }
        }
        System.out.println(-1);
    }