一道java编程题，题目不难但是要注意时间要求

Question

数据可能还挺大的，能帮忙写一个时间复杂度小点的代码吗？
这是我的代码：

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int cnt = scanner.nextInt();
        while(cnt-->0){
            boolean flag = false;
            int num = scanner.nextInt();
            int s4 = num/4;
            int s7 = num/7;
            int i , j=0;
            for (i=0; i<=s4; i++){
                for (j=0; j<=s7; j++){
                    if (i*4+j*7==num){
                        flag = true;
                        break;
                    }
                }
                if (flag) break;
            }
            if (!flag)
                System.out.println(-1);
            else{
                for (int k=0; k<i; k++)
                    System.out.print(4);
                for (int k=0; k<j; k++)
                    System.out.print(7);
                System.out.println();
            }
        }
    }
}

Answer 1

大概给个O(n)的解法，用欧几里得扩展的话，时间复杂度还可以降低，参考链接给了，有兴趣的话，自己看一下

不定方程整数解 扩展欧几里德算法：已知两个不完全为 0 的非负整数 a，b，必然存在整数对 x，y ，使它们满足贝祖等式：解一定存在，根据数论中的相关定理。下面给出代码：int extgcd(int a, int b, int& x, int& y) { int gcd = a; if (b != 0) { gcd = extgcd(b, a % ... https://blog.csdn.net/Originum/article/details/81437027?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522163280890216780269811037%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=163280890216780269811037&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~rank_v31_ecpm-6-81437027.first_rank_v2_pc_rank_v29&utm_term=%E4%BA%8C%E5%85%83%E4%B8%80%E6%AC%A1%E4%B8%8D%E5%AE%9A%E6%96%B9%E7%A8%8B+%E5%90%8C%E4%BD%99&spm=1018.2226.3001.4187

public int getMin(int t){
        if(t<4)
            return -1;
//        4*x+7*y=t
        //思路是，在有解的情况，希望4尽可能的多,7尽可能少,那我们枚举出7的个数，就能进一步求得4的个数了
        //印象中，不定式的整数解是有公式的叫做不定方程的同余公式（欧几里得扩展）
//        (y mod a)/gcd(a,b)
        for(int ky = 0; ky<t; ky+=7){
            int kx = t-ky;
            if(kx%4!=0) continue;
            int ans = 0;
            int x = kx/4;
            int y = ky/7;
            for(int i = 0; i < x; i++){
                ans = ans*10+4;
            }

            for(int i = 0; i < y; i++){
                ans = ans*10+7;
            }
            return ans;
        }

        return -1;
    }