首页 > 试题广场 >

最小的特殊数字

[编程题]最小的特殊数字
  • 热度指数：681 时间限制：C/C++ 5秒，其他语言10秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
用全部N(N<=10)个0-9的数字组成一个“有效”整数（即没有前置0的整数），求这些组成的数中能被K(0<K<10^10)整除的最小数字。

输入描述:
输入分两行，第一行输入N, K，第二行输入N个数字。


输出描述:
输出满足条件的最小的数（不含前置0），如果没有满足条件的数输出 -1。
示例1

输入

4 7
4 0 1 3

输出

1043

说明

413 % 7 = 0， 但是有前置0，所以满足条件的最小数是 1043 % 7 = 0。
示例2

输入

1 142
0

输出

0

备注:
数字中不能使用前置0，例如四个数字0、1、2、3组成的满足条件的最小数不能是0123。
算法知识视频讲解
添加回答
pein531头像 pein531
回溯法求解，为了得到的数最小，要先对候选的n个数进行升序排列，从而保证从小的数进行尝试。
注意：为了将前导0排除掉，我们需要考虑几点：
(1) n不为1，否则一个0其实也是个有效的数；
(2) 当前数nums[i]为0时，需要保证之前没有累加过任何数，这样nums[i]才是前导0，否则高位已经有数了，nums[i]=0是个中间位，不能忽略。 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;

public class Main {
    public static int n;
    public static long k;
    public static int[] nums;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().split(" ");
        n = Integer.parseInt(params[0]);
        k = Long.parseLong(params[1]);
        params = br.readLine().split(" ");
        nums = new int[n];
        for(int i = 0; i < n; i++) nums[i] = Integer.parseInt(params[i]);
        Arrays.sort(nums);
        boolean[] used = new boolean[n];
        System.out.println(dfs(used, 0, 0L));
    }
    
    public static long dfs(boolean[] used, int depth, long num) {
        if(depth == n)
            return num % k == 0? num: -1;
        for(int i = 0; i < n; i++) {
            // 数字用过，跳过
            if(used[i] == true) continue;
            // 前导0跳过
            if(n != 1 && num == 0 && nums[i] == 0) continue;
            used[i] = true;
            long res = dfs(used, depth + 1, num * 10 + nums[i]);
            used[i] = false;
            // 有一个满足就马上返回，保证最小
            if(res != -1) return res;
        }
        return -1;
    }
}

编辑于 2021-08-15 21:19:36 回复(1)
和兆姜头像 和兆姜 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;
ll n, k;
vector<int> nums;
vector<bool> vis;

ll dfs(int use, ll num) {
    if (use == n) {
        if (num % k == 0) return num;
        else return -1;
    }
    for (int i = 0; i < n; i++) {
        if (vis[i] == true) continue;
        if (n != 1 && num == 0 && nums[i] == 0) continue;
        vis[i] = true;
        ll res = dfs(use + 1, num * 10 + nums[i]);
        vis[i] = false;
        if (res != -1) return res;
    }
    return -1;
}

void solve() {
    cin >> n >> k;
    nums.assign(n, 0);
    vis.assign(n, false);
    for (auto& num : nums) cin >> num;
    sort(nums.begin(), nums.end());
    ll res = dfs(0, 0);
    cout << res << endl;
}


int main() {
    int n = 1;
    // cin >> n
    while(n--) solve();
    return 0;
}

发表于 2021-04-11 17:35:24 回复(0)
乌鸦坐航母头像 乌鸦坐航母 
#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n, k;
    cin >> n >> k;
    vector<int> v(n);
    for (int i = 0; i < n; ++i)
        cin >> v[i];
    sort(v.begin(), v.end());
    do {
        if (v.size() > 1 and v[0] == 0)
            continue;
        long long num = 0;
        for (int i : v)
            num = num * 10 + i;
        if (num % k == 0) {
            cout << num;
            return 0;
        }
    } while (next_permutation(v.begin(), v.end()));
    cout << -1;
}
发表于 2022-08-07 09:46:43 回复(0)
wonderson头像 wonderson
不知道为啥，状态压缩DP用不了，去了就没错，应该没啥问题啊，求各位大佬看一下 
import java.util.*;
public class Main {
        static int N = 10;
        static long[] f = new long[1 << N];
        static int n;
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            n = sc.nextInt(); 
            long k = sc.nextLong();
            int[] nums = new int[n];
            for (int i = 0; i < n; i++) {
                nums[i] = sc.nextInt();
            }
            if (n == 1) {
                System.out.println(nums[0] == 0 ? 0 : -1);
                return;
            }
        
                for (int j = 0; j < 1 << n; j++) {
                    f[j] = 0;
                }
            
            Arrays.sort(nums);
            sc.close();
            long res = dfs(nums, 0, k, 0L);
            System.out.println(res);
        }

        private static long dfs(int[] nums, int state, long k, long cur) {
            if (state == (1 << n) - 1) {
                if (cur % k == 0) {
                    return cur;
                } else {
                    return -1;
                }
            }

            long min = Long.MAX_VALUE;
            for (int i = 0; i < n; i++) {
                if (((1 << i) & state) == 0) {
                    if (nums[i] == 0 && state == 0) {
                        continue;
                    }
                    long t = dfs(nums, state | 1 << i, k, cur * 10 + nums[i]);
                    if (t > 0) {
                        min = Math.min(min, t);
                    }
                }
            }
            if (min != Long.MAX_VALUE) {
                f[state] = min;
            } else {
                f[state] = -1;
            }
            
            return f[state];
        }
    }


发表于 2022-05-12 19:51:50 回复(0)
莫里Mori头像 莫里Mori

今天刷到这题，因为N <= 10所有可以DFS解决，注意0<k<=10^10，所以k要开long。

import java.util.*;

public class Main{
    static int N = 15;
    static boolean[] st = new boolean[N];
    static int[] nums = new int[N];
    static int n;
    static long ans = -1, k;
    public static boolean dfs(int u, long path){
        if(u == n){
            if(path % k == 0){
                ans = path;
                return true;
            }
            return false;
        }
        for(int i = 0; i < n; i ++){
            if(st[i]){
                continue;
            }
            if(u == 0 && n != 1 && nums[i] == 0){
                continue;
            }
            st[i] = true;
            boolean flag = dfs(u + 1, path * 10 + nums[i]);
            st[i] = false;
            if(flag){
                return true;
            }
        }
        return false;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        k = sc.nextLong();
        for(int i = 0; i < n; i ++){
            nums[i] = sc.nextInt();
        }
        Arrays.sort(nums, 0, n);
        dfs(0, 0);
        System.out.println(ans);
    }
}
发表于 2021-06-23 09:24:18 回复(0)
C/C++
牛客838902876号头像 牛客838902876号
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

int v[15] = {0};//标记数组
int num[15] = {0};//存储数组
long long result = -1;//初始化结果为-1
long long temp_result[15] = {0};//存储当前数字，0号单元不使用
int N, K;

void dfs(int index)
{
    if(index == N+1)//如果N个数字已经用完，则结束本次深搜
        return;
    int i;
    for (i = 0; i < N; i++)//遍历N个数字，尝试放在下标为index位置
        if (v[i] == 0)//如果下标为i的数字没用过
        {
            v[i] = 1;//标记下标为i的数字用过
            temp_result[index] = temp_result[index-1] * 10 + num[i];//求当前数字
            if(index == N && temp_result[index] % K == 0)//如果N个数字用完并且刚好能够整除
                result = temp_result[index];//更新结果
            dfs(index+1);//继续放下一个数字
            v[i] = 0;//回溯
        }
}

int main()
{
    int i;
    cin>>N>>K;
    for (i = 0; i < N; i++)
        cin>>num[i];
    if (N==1)//如果只有一个数字
    {
        if (num[0] == 0)//如果这个数字是0,则输出结果为0
            cout<<0<<endl;
        else if (num[0] % K == 0)//如果这个数字符合条件，则输出
            cout<<num[0]<<endl;
        return 0;
    }
    sort(num,num+N);//对数字进行排序

    //对N个数字进行全排列，排除前导0
    for (i = 0; i < N; i++)
    {
        if (i==0 && num[i] == 0)//如果N个数字中包含数字0，则从第2个数字开始深搜
        {
            temp_result[1] = num[1];//选择0后面的第一个数字
            v[1] = 1;//标记下标为1的数字已经用过
        }
        else//N个数字中如果不包含0
        {
            temp_result[1] = num[i];//选择下标为i的数字
            v[i] = 1;//标记下标为i的数字已经用过
        }
        dfs(2);//第1个位置已经放了数字，所以从第2个位置开始深搜放数字
    }
    cout<<result<<endl;//输出结果
    return 0;
}

https://blog.csdn.net/Hunter_Kevin/article/details/117637245
发表于 2021-06-07 09:05:21 回复(0)
Python
牛客259340799号头像 牛客259340799号 


N,K=list(map(int,input().split(' ')))
nums=list(map(int,input().split(' ')))
if len(nums)==1 and nums[0]==0:
    print(0)
else:
    nums.sort()
    d=[]
    def f(c,s):
        if len(s)==0:
            if int(c)%K==0:
                d.append(c)

        else:
            for i in range(len(s)):
                if len(c)==0 and s[i]==0:
                    continue
                else:
                    c1=c+str(s[i])
                    s1=s[:i]+s[i+1:]
                    if len(d)!=0:
                        break
                    f(c1,s1)



    f('',nums)
    if len(d)!=0:
        print(d[0])
    else:
        print(-1)

发表于 2021-05-14 20:18:19 回复(0)
牛客12312341头像 牛客12312341
看到数据范围1~10，我直接next_permutation枚举数组全排列，不讲武德。
判断前导为0的情况，注意会爆longlong。 
#include<bits/stdc++.h>

using namespace std;

#define ll long long

ll n;
ll k;
int a[100];
bool ck(ll x){
    int cnt=0;
    if(x==0) cnt=1;
    while(x){
        cnt++;
        x/=10;
    }
    return cnt==n;//如果位数不一样说明有前导0不符合要求
}

int main(){
    cin>>n>>k;
    for(int i=0;i<n;i++) cin>>a[i];
    sort(a,a+n);
    do{
        ll res=0;
        for(int i=0;i<n;i++) res=res*10+a[i];
        if(ck(res)&&res%k==0){
            cout<<res<<endl;return 0;
        }
    }while(next_permutation(a,a+n));
    puts("-1");
    return 0;
}


发表于 2021-04-23 02:29:37 回复(0)
提交观点

问题信息

算法工程师 猿辅导 2021
上传者：小小
难度：
8条回答 1835浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号