An optimized way to find a number that satisfies certain conditions
I've seen this question somewhere. There is an 8-digit number. The first digit from left to right shows the number of zeros in the number. The second number tells you how many 1s there are in the number, the third number tells you how many are 2 and so on, up to the 8th digit, which tells u how many 7 are in the number. Find the number. So I wrote a piece of python code to find out the figure. In addition to the conditions mentioned above, I have several additional checks, such as "the sum of the digits must be 8" and "there is no number 8 or 9 must be present in the number". I have pasted the code below. This is just brute force as I take each number and check the conditions. I was curious to know if there is a better way to solve the problem.
def returnStat(number, digit, count):
number = str(number)
digit = str(digit)
print "Analysing for ",digit," to see if it appears ",count, " times in ",number,"."
actCnt = number.count(digit)
count = str(count)
actCnt = str(actCnt)
if (actCnt == count):
return 1
else:
return 0
def validateNum(number):
numList = str(number)
if '8' in numList:
print "Skipping ",number, " since it has 8 in it"
return (-1)
elif '9' in numList:
print "Skipping ",number, " since it has 9 in it"
return (-1)
elif (sum(int(digit) for digit in numList) != 8):
print "Skipping ",number, " since its sum is not equal to 8"
return (-1)
index = 0
flag = 0
for num in numList:
if (returnStat(number,index,num)) :
index = index+1
continue
else:
flag = 1
break
if (flag == 1):
return (-1)
else:
return number
for num in range(0,80000000):
number = '{number:0{width}d}'.format(width=8,number=num)
desiredNum = "-1"
desiredNum = validateNum(number)
if (desiredNum == -1):
print number," does not satisfy all "
continue
else:
print "The number that satisfies all contition is ",number
break
source to share
Even if you iterate over all 8-digit numbers without 8 or 9 in them, there isn't much possibility (in fact, 8 ^ 8 = 1 <24 ~ = 17 million).
Here's a naive program that tries them all:
import itertools
for digs in itertools.product(range(8), repeat=8):
counts = [0] * 8
for d in digs:
counts[d] += 1
if counts == list(digs):
print digs
It exits (with one solution) in 15 seconds on my machine.
To make it faster, you can only consider 8-digit numbers up to 8. This is the same code as before, but now it is used sum_k
to create opportunities. ( sum_k(n, k)
generates all n
-digue tuples where all digits are less than 8, which are added to k
).
def sum_k(n, k):
if k < 0 or n * 7 < k: return
if n == 1:
yield k,
return
for d in xrange(8):
for s in sum_k(n-1, k-d):
yield (d,) + s
for digs in sum_k(8, 8):
counts = [0] * 8
for d in digs:
counts[d] += 1
if counts == list(digs):
print digs
This code completes in 0.022 seconds on my machine.
Adapting the code to solve the general case gives the following solutions:
1210 2020 21200 3211000 42101000 521001000 6210001000 72100001000 821000001000 9210000001000
source to share
You can go further than just saying that the numbers 8 or 9 are not possible.
Can the last digit be greater than 0? The answer is no. If the last digit is 1, it means there is another one elsewhere. However, if there is 7, it means that the same number happened 7 times. This is clearly not possible. So the last digit must be 0.
So we have xxxxxxx0.
How about the second to the last digit?
If xxxxxx10, then there must be at least one value 6, which means that the same number happened 6 times. We can try 60000010, but that is not correct, because there is a 1 that should be reflected in the second digit. The second digit cannot be higher than 1, because 2 means that there are 2 sixes, which in turn means that one number happened six times, while another number also happened 6 times, which is impossible.
So we have xxxxxx00.
If xxxxx100, then there must be at least one value 5, which means that the same number happened 5 times. Let's start with 51000100. Almost, but there are 2 seconds. So it should be 52000100. But wait, now there is one 1. and one 2. So we are trying 52100100. But now we only have 4 0s. We cannot have xxxxx200 because that means there are 2 5s, which is not possible as explained above.
So we have xxxxx000.
If xxxx1000 we can try 40001000, nope, 41001000, nope, 42101000.
The way it is. 42101000.
source to share