sajeed66999's blog

Beautiful Number
By sajeed66999, history, 3 years ago, In English

You are given a number N. A number is called beautiful if, for every digit x in the number, there are x occurrences of it in the number.

Example:

1 is beautiful because 1 has 1 occurrence. 3133 is beautiful because 1 has 1 occurrence and 3 has 3 occurrences. 224 is not beautiful because 4 does not have 4 occurrences. Find the smallest beautiful number which is greater than N

Example: N=299 Output: 333

def solve(N):
    n=list(str(N))
    d={}
    for i in n:
        if i in d:
            d[i]+=1
        else:
            d[i]=1
    for i in d:
        if int(i)!=d[i]:
            return False
    return True
def beautifulNumber (N):
    i=1
    while(True):
        if solve(N+i):
            return(N+i)
        i=i+1
N = int(input())
print(beautifulNumber(N))

constraints: 1<N<10^12

Code takes a lot of time for huge numbers like 10^10. need it optimized.

  • Vote: I like it
  • -39
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
3 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

There are much less than $$$2^9 \cdot 9! = 185794560$$$ such numbers. So you can precalculate them.

UPD: Any proof that it isn't an ongoing contest?

→ Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Why don't you use list.count()? Like:

for i in n:
    if n.count(i)!=i:
        return false
return true

This method's complexity depends on the number of digits in N. You can read this page for more information.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Still won't be optimal as we are checking every number

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Yes, but N have at most 9 distinct digits and just add the checked digit to a list like the one you have done before so we can decrease the complexity.

      → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    hey mate, n.count() works in O(n) and the total complexity of this code till be i guess O(n^n) correct me if i am wrong, this will work fine on a small constraints but he mentinoed that 1<N<10^12

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, it just searches from the beginning to the end of the list but as I mentioned, you can add searched digits to a list and then don't need to check them again. And, there are at most 9 distinct digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 right? So in the worst case, our solution's complexity is O(n^9) which n is the number of digits in N. (1<N<10^12 so it is at most 12 digits).

      → Reply
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

This question is a part of an online coding challenge by a Company. You should ask it after the contest is over.

→ Reply