首页 > 试题广场 >

最后一位

[编程题]最后一位

热度指数：204 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

牛牛选择了一个正整数X,然后把它写在黑板上。然后每一天他会擦掉当前数字的最后一位,直到他擦掉所有数位。在整个过程中,牛牛会把所有在黑板上出现过的数字记录下来,然后求出他们的总和sum.
例如X = 509, 在黑板上出现过的数字依次是509, 50, 5, 他们的和就是564.
牛牛现在给出一个sum,牛牛想让你求出一个正整数X经过上述过程的结果是sum.

输入描述:

输入包括正整数sum(1 ≤ sum ≤ 10^18)

输出描述:

输出一个正整数,即满足条件的X,如果没有这样的X,输出-1。

示例1

输入

输出

算法知识视频讲解

hey,20180424

思路是反向推，数number有n位，除以 n个1得到的是最前面那位，比如564是3位，就是除以111,

564 / 111 = 5 ，所以X的第一位是5， 564 - 5*111 = 9

9 / 11 =0，所以X的第二位是0， 9 - 0*11=9

9 / 1 =9 ，所以第三位是9.

理由是如果正着算是 509+509/10+509/100=564，用数学最简单的通分一写就明白了。

然后考虑什么时候没有对应的X值，就是最后一位剩下的是超过9的数，比如565，自己按上面的步骤写一下就懂了。

下面附上代码，菜鸟写的不好请见谅。

#include<iostream>

#include<cmath>
using namespace std;
typedef long long ll;

int getDigit(ll num) {
    int digit = 0;
    while (num > 0) {
        digit++;
        num /= 10;
    }
    return digit;
}
ll nOne(int digit) {
    ll num=0;
    for (int i = 0; i < digit; ++i) {
        num += ll(pow(10, i));
        //这里一定要加上long long的强制转换否则1e+17会有偏差
    }
    return num;
}
int main() {
    ll num;
    cin >> num;
    int digit = getDigit(num);
    int *pNum = new int[digit];
    for (int i = 0; i < digit; ++i) {
        ll digitOne = nOne(digit - i);
        pNum[i] = num / digitOne;
        if (pNum[i] > 9 ) {
            cout << -1 << endl;
            return 0;
        }
        num -= pNum[i] * digitOne;
    }
    for (int i = 0; i < digit; ++i)
        cout << pNum[i];
    cout << endl;
}

发表于 2018-10-08 19:58:34 回复(0)

Java

倔强小柱子☀

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long X = sc.nextLong();
        int length=String.valueOf(X).length();
        long a=fun(length,X);
        long b=fun(length-1,X);
        if(a==-1&&b==-1)
            System.out.println(-1);
        else if(a!=-1)
            System.out.println(a);
        else if(b!=-1)
            System.out.println(b);
    }

    /**
     * 获得长度为length，每一位都为num的数字
     * @param length
     * @param num
     * @return
     */
    public static long get_num(int length,int num){
        long ans=0;
        for(int i=1;i<=length;i++){
            ans=ans*10+num;
        }
        return ans;
    }
    public static long fun(int length,long X){
        long ans=0;
        for(int j=length;j>0;j--){
            for(int k=9;k>=0;k--){
                if(X>=get_num(j,k)){
                    X-=get_num(j,k);
                    ans=ans*10+k;
                    break;
                }
            }
        }
        return X==0?ans:-1;
    }

}

通过全部用例

发表于 2022-03-22 16:58:12 回复(0)

蔡路政

// 1_最后一位.cpp: 定义控制台应用程序的入口点。
//

#include<iostream>

using namespace std;

long long solve(long long num) {
    long long len = 0, one = 0, copyNum = num;
    while (copyNum) {
        len++;
        one = one * 10 + 1;
        copyNum /= 10;
    }

    long long ans = 0;
    while (len && one) {
        long long temp = num / one;
        if (temp > 9) {
            return -1;
        }
        ans = ans * 10 + temp;

        num -= temp * one;
        one /= 10;
        len--;
    }
    return ans;
}

int main()
{
    long long num;
    cin >> num;
    long long ans = solve(num);
    cout << ans;
    system("Pause");
return 0;
}

发表于 2018-10-08 21:47:24 回复(0)