You're my hero. Thanks for the tip!!

It's a great solution. If I understand correctly, you separate N in two numbers: a multiple of 3 and a multiple of 5.

Is there a name to this mathematical procedure ?

test case not running properly

Great one, just simplisitc.

GENIUS!

Clever!

Thanks man. Helped me with my solution.

Its a great and simple solution. Thanks for tips.

Amazing! Very clever! I didn't account for the possibility of large numbers before, but your solution totally avoids the problem. It's impressive how such a simple problem can teach you important lessons. Thanks!

Thank you for the explanation. This is by far the best tip I have come across. I was going in another direction because of the word permutation. You are my hero as well!

What would happen if you did it the other way? Keep subtracting by 3 until it is divisible by 5? I am assuming that would be the method of solution if you needed a multiple of 5 for "5"'s and a multiple of 3 for "3"'s?

Testing, comment didn't show up

If i input 7... It will decreese 10 .. then it will be a minus value..

awesome solution thanks a lot!!

do it in java aq

You can use a much less 'clever' solution with a deterministic limit by pre-calculating the maximum product of integer division (ie floor) of input//3, input//5. It only uses 2 division operations. All the rest are multiplication. The slowest tests are .1s but Javascript isn't exactly optimized for raw calculation performance.

Can someone explain how this works? I don't understand how subtracting 5 "x" times makes the number a multiple of 3.

I am really having difficulty understanding this. Can someone give me an ELI5 explanation?

if(z<0 and z!=0): print '-1' this is required I guess. but this simple code is showing timeouts and is unable to find out the ans for 99946. whereas 46/946/9946 are cool.

Thank you, this was very helpful!!

my test cases are ran out of time.

Awesome Solution. Thank you for the logic.

can you give your implemention ?

In every sense of the word, this solution is terse. Well done!

Your advice really helped me a lot reaching a solution :)

I loved it,but i want to know what made you to try this kind of logic if we need to do with 3,7 instead of 3,5 with respective rules. how can find logics for this kind of questions?

This is indeed a best solution for this problem, but is there anyone who can explain why this correlation exists between reminder and amount of subtraction?

Thank you very much theroadtaken123

Thank you very much for sharing the logic. I tried implementing it using cpp. Working fine for small cases.

int main(){ int t; cin >> t; for(int a0 = 0; a0 < t; a0++){ int n, y, z, flag = -1; cin >> n; z = n; if(z <= 0) cout<<"-1\n"; else { if(z%3 == 0) { cout<< string(z,'5')<<"\n"; } while(z%3 != 0) { z -= 5; if(z<0) { cout<<"-1\n"; break; } else { cout <

But it prints some crap for cases like 100,121,etc Did i messed some thing with your logic?? Any suggestions plz. Thank you ...

Why are you putting a solution in the discussion?

sallute!!

Thanks Man. This code is really helpful

I didn't pass the last 2 test cases and got a run time error for the last test case. Could anyone find the bug in my solution?

import java.io.; import java.util.;

public class Solution {

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int T = sc.nextInt();
    String out = "";
    while(T-- > 0) {
        int key = sc.nextInt();
        if(key % 3 == 0) {
            out = new String(new char[key]).replace("\0", "5");
        }
        else {
            int x = key;
            while(x % 3 != 0 && x > 0) {
                x -= 5;
            }
            if(x%3 == 0) {
                String fives = new String(new char[x]).replace("\0", "5");
                String threes = new String(new char[key-x]).replace("\0", "3");
                out = fives+threes;
            }
            else if(x == 0) {
                out = new String(new char[key]).replace("\0", "3");
            }
            else out = "-1";
        }
        System.out.println(out);
    }
}

}

what if the number is even??

Thannk you very much!!!

nice solution, thnx!

nice solution, thnx!

Sorry, I still don't get why you chose to subtract from 5? Please explain.

Superb solution !! thanks

What if the input is 10? we get wrong answer.

I'm confused about 4. How would this work for 4? z%3 would not equal 0 but z-=5 would be -1. I could understand how it could work for all other cases I can think of.

Hi theroadtaken123 where you able to runt he test cases ?

Great Solution....Thanks

I try in c++ and php, both dont work, and the error is "truncated", what i do?

Thanks! Very smart! :D

Extension for Swift to multiply Strings/Characters. Don't forget to unwrap the optional.

extension String {
	public init?(byRepeatingString str: String, count: Int) {
		var newString = ""

		for _ in 0 ..< count {
			newString += str
		}

		self.init(newString)
	}
}

You don't need while loop. You only need 2 iterration because z%3 = (z-15)%3, (z-5)%3 = (z-20)%3, ...

Really awesome technique. Hats off to you.

Simply Awesome :)

Thanks ;)

this is the best solution. try to find the largest number of digits which is divided by 3 and put corresponding number 5 at the begin of result.

this is an old discussion but is there any suggestions about this sol in c /**/ void repeat_char(char c , int co ) { for (int i=0; i < co; i++ ) { printf("%c", c); } } int main(){ int t; scanf("%d",&t); int n[t]; for(int a0 = 0; a0 < t; a0++){ scanf("%d",&n[a0]); } for(int a0 = 0; a0 < t; a0++){
int num5 = n[a0] - n[a0] %3; int num3 = n[a0] - num5; switch(num3 % 5){ case 1: num3 = 10;break; case 2: num3 = 5;break; case 3: num3 = 15;break; case 4: num3 = 10;break; } if(num3>n[a0]){ printf("-1\n");
continue; } num5 = n[a0] - num3; if(num5>0) repeat_char('5',num5); if(num3>0) repeat_char('3',num3); printf("\n");

}
return 0;

}

Awesome bro! How did you reach to this solution?

Hey guys, can someone please help me out as to why this is not working? Would appreciate any help. Thanx.

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int t = in.nextInt();
    for(int a0 = 0; a0 < t; a0++){
        int n = in.nextInt();int m;
        String x="";
        if(n%3==0){
            for(int i=0;i<n;i++){
                x=x+"5";
            }
            System.out.println(Long.parseLong(x));
        }
        else{
            for(m=n;m%5!=0;){
                m=m-3;
                if(m<0)
                    break;
            }
            if(m<0){
                System.out.println(-1);
                continue;
            }
            else{
                for(int i=m;i<n;i++){
                    x=x+"5";
                }
                for(int i=0;i<m;i++){
                    x=x+"3";
                }
                System.out.println(Long.parseLong(x));
            }
        }
    }
}

No need for repeated subtractions or loops. It's purely O(1) (just straightforward formula split in two parts, two calculations).

int q = ((3-(N%3))%3) *5;
if (N-q < 0)
	cout << -1 << endl;
else
	cout << string(N-q,'5') << string(q,'3') << endl;

There's no need of the while loop anyway, search for my solution down below.

Superb bro!!

_/_

i don't get it. can you explain in simpler way?

Thanks a lot. Great way ;)

C++ solution-->

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    int t, n, flag = 0;
    cin >> t;
    for(int i = 0; i < t; i++){
        cin >> n;
        int z = n;
        while(z % 3 != 0){
            z -= 5;
            if(z < 0){
                cout << "-1" << endl;
                flag++;
                break;
            }
        }
        if(flag == 1){
            flag = 0;
        }else{
            cout << string( z, '5') << string( n-z, '3') << endl;
        }
    }
    return 0;
}

The theory your running is close. I think you mis-explain it, given that you actually passed the test cases.

modulo 1: 5 needs to be subtracted 9 times; modulo 2: 5 needs to be subtracted 3 times. Remember, 5 needs to appear a number of times divisible by 3. If the current number is divisible, and you remove 1 or 2, the resulting number can not mathematically be divisible by 3.

You also need to add an additional check to make sure that you actually have enough 5s to remove the required number. If not, that should be the only case where you can not make a proper number, resulting in a "-1".

Only maths can do it!!.Thanks for the tip!!

getting terminated due to timeout plzz help

Java 8

    static String aDecentNumber(int n) {
        int temp = n;
        while (temp >= 3) {
            if (temp % 3 == 0) {
                return fillNo(5, temp) + fillNo(3, n - temp);
            }
            temp -= 5;
            if (temp == 0) {
                return fillNo(3, n);
            }
        }
        return "-1";
    }

    static String fillNo(int no, int times) {
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < times; i++) {
            sb.append(no);
        }
        return sb.toString();
    }

C++ solution :

void decentNumber(int n) {
    int tmp;
    for (int x=0;x<=n/5;x++)
    {
        if (!((n-x*5)%3))
        {
            tmp=(n-x*5)/3;
            while(tmp--)    cout << 555;
            while(x--)  cout << 33333;
            cout << endl;
            return;
        }
    }
    cout << -1 << endl;
    return;
}

Thanks man. Now all the test cases are accepted.

Wow... didn't know how powerful StringBuilder is. Thank you!

MVP :')

Thanks!!

Wow, thank you for your comment. I spent like 5 hours or so messing with my code before coming here and finding this comment. I had tried finding larger strings to try to append together (e.g. adding three 5's at a time versus one 5) and that made it faster but not enough. But then you enlightened me, thank you so much.

That was very helpful! But I didnot use StringBuilder. I printed the numbers inside loop and printed a new line after the loop.

Solved my timeout problem. Thank you!

Thanks a lot, solved my timeout issue! Here is a virtual cookie for you! :D

Cookie cookie = new Cookie("thanks","please have this cookie");
HttpServletResponse tummy = new HttpServletResponse();
tummy.add(cookie);

StringBuilder saved my marriage and helped my kids get through college. Thank you StringBuilder!

Thanks.My test cases are now accepted.

String appending indeed is a problem, string builder is so much better, thanks for your tip!

Hey man, I didnt know how StringBuilder worked, but still got the solution reducing the number of iterations.

public static void main(String[] args) {

    Scanner in = new Scanner(System.in);
    int t = in.nextInt();

    for (int i=0;i<t;i++){

        int n = in.nextInt();
        String sol3 = "", sol5 = "";
        String staux = "555";

        while(n>0){
            if (n%3==0)
                break;                                    
            else{                    
                sol3+="33333";
                n-=5;                    
            }
        }            

        while (n>0){

            if (staux.length()<=n){
                sol5+=staux;
                n-=staux.length();
                staux+=staux;
            }
            else
                if (n<3) 
                    break;
                else
                    staux="555";

        }

        if (n==0)
            System.out.println(sol5+sol3);
        else
            System.out.println(-1);

    } 
}

Still much better using Stringbuilder, but not impossible with strings ;) Thanks for the info.

Same tip for the C# crowd. Strings are immutable; go with the StringBuilder

hahah nice ad..

Same for C#. I just wasted 1 hour by doing string concatenations and getting timeouts. Honestly man, even after learning string theory a dozen times, I still forget that strings are immutable.

Thanks man.

I feel you. I spent waaay more time with this than I wanted to. But hey, now we're smarter!

am i missing somethign here? The editorial solution is O(1) how is this faster?

It fails in some cases for ex: when N=1000 :P. PS: adding if(pivot%3!=0) pivot=getPivot(pivot); before checking for if(pivot<0) solves the prolem.

yeah finding the pivot is important. My solution is similar. I aimed to remove the expensive operation "modulo", here's my solution.

#Python solution without modulo
t = int(input().strip())
for a0 in range(t):
    n = int(input().strip())
    x = (int(n / 3)) * 3
    y = 0
    while True:
        y = n - x
        if ((int(y / 5)) * 5 != y):
            if (x == 0):
                print("-1")
                break
            x = (int((x - 1) / 3)) * 3
        else:
            print (int(x) * "5" + int(y) * "3")
            break

Can someone please explain the code for me especially the "getPivot" function? I don't get it...

Apparently HackerRank is truncating all output after 32767 total characters (on all lines combined). Perhaps someone needs to check the output box to see what its limit is.

I'm running into the same issue. Downloaded a few of the failed test cases only to find out that my algorithm actually works... lame!

Nice!!!

what's the java version of this?

A not as pretty JS version:

 if (n%3==0 && n!=0) {  
     console.log( Array(n+1).join("5"));
 } else if (n%3==1 && n>=10) {
     console.log(Array((n-10)+1).join("5")+Array(10 + 1).join("3"));
} else if (n%3==2 && n>=5){
    console.log(Array((n-5)+1).join("5") + Array(5+1).join("3"));
} else {
    console.log('-1');
}

thanks that was really helpful :)

I'm also getting 5-13 test cases as time-outs. Did you figure out what is causing the problem?

lovely!