Найдите ближайшее число определенного числа, у которого есть определенная цифра (7)

Question

Найдите ближайшее число определенного числа, у которого есть определенная цифра (7)

Ну, я должен написать программу, чтобы найти БЛИЖАЙШЕЕ число заданного числа N, которое имеет ровно «K» 7s.

Например, если input это:

N K
1773 3

Выход:

О, еще одна вещь, что N может быть максимум 100 000 000 000 000, будет ли долго долго хватать, чтобы справиться с этим?

Мой код пока не работает 🙁

#include <iostream>
using namespace std;
int main()
{
unsigned long long a, i;
int b, num=0, dig, tmp;
cin>>a>>b;
i=a+1;
do
{
num=0;
tmp=i;
while (tmp>0)
{
dig=tmp%10;
tmp=tmp/10;
if (dig==7)
num++;
}
i++;
}
while(num<b);
cout<<i-1;
return 0;
}

1

arrays c++digit numbers

Решение

Другие решения

Некоторые проблемы:

ans=i записывает некоторые i после того, как вы поделили его несколько раз, вам нужно записать оригинал i
Вы только петли в 1 направлении, вы должны проверить в обоих направлениях одновременно
Цикл по всем числам в принципе слишком медленный
- Если число составляет 100 000 000 000 000, а k = 14, вам необходимо проверить 22 222 222 222 223 (100 000 000 000 000-77 777 777 777 777) номеров, что недопустимо

Примечание — максимальная длинная длинная — 9223372036854775807..

Вот некоторый псевдокод, который должен работать:

num = number of 7s in input
if (num == k)
print input
if (num < k)
a = input with (k-num) non-7 digits from least significant digit set to 7
let x = last position set
b = substring(input, 1, position)
c = b + 1
d = b - 1
ba = concat(b, substring(a, position, end))
ca = concat(c, substring(a, position, end))
da = concat(d, substring(a, position, end))
if (abs(input - ba) <= abs(input - ca) &&
abs(input - ba) <= abs(input - da))
print b
else
if (abs(input - ca) <= abs(input - ba) &&
abs(input - ca) <= abs(input - da))
print c
else
print d
if (num > k)
x = (k-num)th 7 from least significant digit
a = input with x set to 6 and all less significant digits to 9
b = input with x set to 8 and all less significant digits to 0
if (input - a > b - input)
print b
else
print a

1

Как насчет этого алгоритма?

Преобразуйте число в строку.
Посчитайте количество 7 в нем.
Если у него меньше 7 с, чем K, поменяйте числа справа налево на 7 с по одному, пока не будет достигнуто K, затем перейдите к шагу 5.
Если у него больше 7 с, чем K, измените числа справа налево на 6 с по одному, только если они равны 7, пока не будет достигнуто K, затем перейдите к шагу 5.
Преобразуйте его обратно в целое число.

long long можно использовать в соответствии с ответом Dukeling.

0

Источник

Accepted Answer

Ваша проблема не проблема программирования, а математическая проблема.

Позволять m = 1+E(log10(N))т.е. количество цифр в десятичной записи N (вероятно, будет быстрее вычислить его путем подсчета цифр, чем с помощью логарифма).

Позволять mK быть числом 7 в N,

Позволять N' быть выходным номером.

Я вижу 4 случая:

K >= m : затем N' = 7..7 (K цифр).
K == mK : затем N' = N,
K > mK and K < m : тогда вы заменяете все7 цифры с 7начиная с наименее значимых цифр. Пример: N = 1 357 975 , K = 4 => N' = 1 357 777, Предупреждение: есть особый случай, если у вас есть 8Пример: N = 80, N' = 79, Вы можете сделать это, используя общий префикс, а затем сгенерировав все 7 суффикс (особый случай: удалите еще один из префикса и добавьте 7 9 7 7 ... 7). Увидеть special case в коде.
K < mK : есть два возможных числа.

Позволяет разложить N: N = a1 a2 ... ap 7 b1 b2 ... bq, где
- a1 ... ap являются p числа в [0..9] а также
- b1 ... bq являются q числа в [0..9] \ {7}
Позволять A = a1 ... ap 6 9 ... 9 а также B = a1 ... ap 8 0 ... 0 (q цифры после 6или 8). Затем, N' = closestToN(A,B), Если оба числа одинаково близки, выбор за вами.

Извините за плохое математическое форматирование.
Код теперь может быть более простым для написания. Вот моя реализация:

#include <iostream>

unsigned long long getClosestWith7(unsigned long long n, unsigned int k)
{
// Count number of digits
unsigned long long tmp = n;
unsigned int m = 0, mK = 0;
while(tmp > 0)
{
if(tmp % 10 == 7) mK++;
tmp /= 10;
m++;
}

// Distinct cases
if(k == mK && n != 0)
return n;
else if(k >= m || n == 0) // implicit: k != mK
{
unsigned long long r = 0;
while(k > 0)
{
r = 10 * r + 7;
k--;
}
return r;
}
else if(k > mK) // implicit: k != mK, k < m
{
unsigned long long r = n;
unsigned long long s = 0;
m = 0;
while(mK < k)
{
if(r % 10 != 7) mK++;
r /= 10;
m++;
}
if(r % 10 == 8) // special case
s = 79 + 100 * (r / 10);
while(m > 0)
{
r = 10 * r + 7;
if(s != 0 && m > 1) // special case
s = 10 * s + 7;
m--;
}
return (r < n && n - r < n - s) || (r >= n && r - n < n - s) ? r : s;
}
else // implicit : k < mK
{
// Generate a and b
unsigned long long a = n;
unsigned long long b = 0;
m = 0;
while(mK > k)
{
if(a % 10 == 7) mK--;
a /= 10;
m++;
}
b = 10 * a + 8;
a = 10 * a + 6;
m--;
while(m > 0)
{
a = 10 * a + 9;
b = 10 * b + 0;
m--;
}

// Compare (return lowest if equal)
return n - a <= b - n ? a : b;
}
}

#define CLOSEST7( N , K ) \
std::cout << "N = " << N << ", K = " << K << " => N' = " << getClosestWith7(N,K) << "\n"
int main()
{
CLOSEST7(1773,3);
CLOSEST7(83,1);
CLOSEST7(17273,3);
CLOSEST7(1273679750,6);
CLOSEST7(1773,1);
CLOSEST7(83,5);
CLOSEST7(0,2);
CLOSEST7(0,0);
}

На ваш вопрос о long long: это зависит от компилятора. Зачастую размер этого типа составляет 64 бита, поэтому вы можете хранить число от 0 до 2 ^ 64 — 1 (без знака), которое равно 18 446 744 073 709 551 615, поэтому в большинстве реализаций оно должно соответствовать вашему диапазону данных. ,

2