Find the nearest number of specific number which has specific digit (7)

Question

Well, I have to write a program to find the NEAREST number of given number N which has exactly "K" 7s.

For example, if input is:

N K
1773 3

Output:

1777

Oh, one more thing is that N can be 100 000 000 000 000 maximum, will long long be enough to handle this?

My code so far which is not working :(

#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;
}

Answer 1

Your problem is not a programming problem but a math problem.

Let m = 1+E(log10(N)), ie the number of digits in the decimal writing of N (it will be probably faster to compute it by counting digits than using a logarithm).

Let mK be the number of 7 in N.

Let N' be the output number.

I see 4 cases:

• K >= m : then N' = 7..7 (K digits).
• K == mK : then N' = N.
• K > mK and K < m : then you replace all non-7 digits with 7, starting from the least significant digits. Ex: N = 1 357 975 , K = 4 => N' = 1 357 777. Warning : there is a special case, if you have a 8, ex: N = 80, N' = 79. You can do this case by using a common prefix, and then generating an all 7 suffix (special case: remove one more from the prefix and add 7 9 7 7 ... 7). See special case in the code.

• K < mK : there are two possible numbers.

  Lets decompose N: N = a1 a2 ... ap 7 b1 b2 ... bq, where

  • a1 ... ap are p numbers in [0..9] and
  • b1 ... bq are q numbers in [0..9] \ {7}

  Let A = a1 ... ap 6 9 ... 9 and B = a1 ... ap 8 0 ... 0 (q digits after the 6or the 8). Then, N' = closestToN(A,B). If both numbers are equally close, the choice is up to you.

Sorry for the bad math formatting. The code can now be more easy to write. Here is my implementation:

#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);
}

For your question about long long: it depends on the compiler. Often, the size of this type is 64 bits, so you can store number from 0 to 2^64 - 1 (unsigned), which is 18 446 744 073 709 551 615, so it should be ok for your data range on most implementations.

Answer 2

How about this algorithm?

1. Convert the number into a string.

2. Count the number of 7s in it.

3. If it has less 7s than K, change the numbers from the right-most to left into 7s one-by-one until K is reached, then go to step 5.

4. If it has more 7s than K, change the numbers from the right-most to left into 6s one-by-one only if they are 7, until K is reached, then go to step 5.

5. Convert it back into an integer.

long long is usable according to Dukeling's answer.

Answer 3

Some problems:

• ans=i records some i after you've divided it a few times, you need to record the original i
• You only loop in 1 direction, you need to check in both directions at the same time
• Looping through all numbers is fundamentally too slow
  • If the number is 100 000 000 000 000 and k = 14, you'd need to check 22 222 222 222 223 (100 000 000 000 000-77 777 777 777 777) numbers, which is not viable

Side note - the maximum for long long is 9223372036854775807.

Here is some pseudo-code which should work:

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