Using seven segment display, you can write down any digit from 0 to 9 using at most seven segments. Given a positive number N and then a string S representing a number of N digits. You have to rearrange the segments in this N digit number to get the smallest possible N digit number. This number can have leading zeros. You can not waste any segment or add any segment from your own. You have to use all of the segments of the given N digits. 
Note: You can refer this diagram for more details
Example 1:
Input:
N = 6
S = "234567"
Output:
000011
Explanation:
234567 has a total of 28 segments and
we can rearrange them to form 000011
which has 28 segments too. 000011 is the
smallest possible number which can be
formed on rearrangement.
Example 2:
Input:
N = 3
S = "011"
Output:
011
Explanation:
011 has a total of 10 segments and this
is the smallest number with 10 segments.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function sevenSegments() which takes an Integer N and a String S of length N as input and returns the smallest possible N digit number which can be made using all of the segments given.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
 
Constraints:
1 <= N <= 10^{4}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Mathematics

Greedy algorithms

Starter code: #User function Template for python3



class Solution:

    def sevenSegments(self, S, N):

        # code here 

Solutions:
class Solution:

	def sevenSegments(self, S, N):
		segs = [6, 2, 5, 5, 4, 5, 6, 3, 7, 5]
		total = sum((segs[int(S[i])] for i in range(N)))
		ans = ['0'] * N
		for i in range(N):
			if total == 2 * (N - i):
				ans[i] = '1'
				total -= 2
			elif total == 7 * (N - i):
				ans[i] = '8'
				total -= 7
			elif total - 6 >= 2 * (N - i - 1) and total - 6 <= 7 * (N - i - 1):
				ans[i] = '0'
				total -= 6
			elif total - 2 <= 7 * (N - i - 1):
				ans[i] = '1'
				total -= 2
			elif total - 3 <= 7 * (N - i - 1):
				ans[i] = '7'
				total -= 3
			elif total - 4 <= 7 * (N - i - 1):
				ans[i] = '4'
				total -= 4
			elif total - 5 <= 7 * (N - i - 1):
				total -= 5
				ans[i] = '2'
		return ''.join(ans)


class Solution:

	def sevenSegments(self, s, n):
		segs = {'0': 6, '1': 2, '2': 5, '3': 5, '4': 4, '5': 5, '6': 6, '7': 3, '8': 7, '9': 5}
		ds = [0, 1, 2, 4, 7, 8]
		es = [6, 2, 5, 4, 3, 7]
		ns = sum([segs[c] for c in s])
		for i in range(n):
			seg = 6 * (n - 1 - i)
			res = self.step(s, n, ns, ds, es, 0, seg, i)
			if not res is None:
				return str(res).zfill(n)

	def step(self, s, n, ns, ds, es, val, seg, i):
		if i < 0:
			return val if seg == ns else None
		a = seg + (i + 1) * 2
		b = seg + (i + 1) * 7
		if ns < a or b < ns:
			return None
		for j in range(6):
			d = ds[j]
			e = es[j]
			res = self.step(s, n, ns, ds, es, val + 10 ** i * d, seg + e, i - 1)
			if not res is None:
				return res


class Solution:

	def sevenSegments(self, S, N):
		segments = {'0': 6, '1': 2, '2': 5, '3': 5, '4': 4, '5': 5, '6': 6, '7': 3, '8': 7, '9': 5}
		values = {2: '1', 3: '7', 4: '4', 5: '2', 7: '8'}
		summa = 0
		for item in S:
			summa += segments[item]
		result = []
		while summa > N * 6:
			result.append('8')
			summa -= 7
			N -= 1
		while summa - 6 >= (N - 1) * 2:
			result.append('0')
			summa -= 6
			N -= 1
		while N > 1:
			result.append('1')
			summa -= 2
			N -= 1
		if summa:
			result.append(values[summa])
		return ''.join(sorted(result))


class Solution:

	def sevenSegments(self, S, N):
		hmap = {}
		hmap[0] = 6
		hmap[1] = 2
		hmap[2] = 5
		hmap[3] = 5
		hmap[4] = 4
		hmap[5] = 5
		hmap[6] = 6
		hmap[7] = 3
		hmap[8] = 7
		hmap[9] = 5
		seg = 0
		for i in S:
			seg += hmap[int(i)]
		ans = []
		for i in range(N):
			ans.append('1')
			seg -= 2
		for j in range(N):
			if seg == 4:
				ans[j] = '0'
				break
			elif seg > 4:
				ans[j] = '0'
				seg -= 4
			elif seg < 4:
				if seg == 3:
					ans[-1] = '2'
				elif seg == 2:
					ans[-1] = '4'
				elif seg == 1:
					ans[-1] = '7'
		if seg > 0:
			k = N - 1
			while seg and k >= 0:
				last = hmap[int(ans[k])]
				newseg = last + 1
				if str(newseg) == '7':
					ans[k] = '8'
				seg -= 1
				N -= 1
		ans = ''.join(ans)
		return ans


class Solution:

	def sevenSegments(self, s, n):
		segs = {'0': 6, '1': 2, '2': 5, '3': 5, '4': 4, '5': 5, '6': 6, '7': 3, '8': 7, '9': 5}
		ds = [0, 1, 2, 4, 7, 8]
		es = [6, 2, 5, 4, 3, 7]
		ns = sum([segs[c] for c in s])
		for i in range(n):
			seg = 6 * (n - 1 - i)
			res = self.step(s, n, ns, ds, es, 0, seg, i)
			if not res is None:
				return str(res).zfill(n)

	def step(self, s, n, ns, ds, es, val, seg, i):
		if i < 0:
			return val if seg == ns else None
		a = seg + (i + 1) * 2
		b = seg + (i + 1) * 7
		if ns < a or b < ns:
			return None
		for j in range(6):
			d = ds[j]
			e = es[j]
			res = self.step(s, n, ns, ds, es, val + 10 ** i * d, seg + e, i - 1)
			if not res is None:
				return res
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		S = input()
		ob = Solution()
		print(ob.sevenSegments(S, N))


class Solution:

	def sevenSegments(self, S, N):
		dic = {'0': 6, '1': 2, '2': 5, '3': 5, '4': 4, '5': 5, '6': 6, '7': 3, '8': 7, '9': 5}
		count = 0
		for i in range(N):
			count += dic[S[i]]
		res = []
		for i in range(N):
			res.append('1')
			count -= 2
		for j in range(N):
			if N == 1:
				res[j] = S[0]
			elif count == 4:
				res[j] = '0'
				break
			elif count > 4:
				res[j] = '0'
				count -= 4
			elif count < 4:
				if count == 3:
					res[-1] = '2'
				elif count == 2:
					res[-1] = '4'
				elif count == 1:
					res[-1] = '7'
		return ''.join(res)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		S = input()
		ob = Solution()
		print(ob.sevenSegments(S, N))


class Solution:

	def sevenSegments(self, s, N):

		def getsmaller(d, count):
			for x in d:
				if d[x] == count:
					return str(x)
		d = {0: 6, 1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 5}
		if len(s) == 1:
			return getsmaller(d, d[int(s)])
		maxx = 0
		for x in s:
			maxx += d[int(x)]
		arr = ['1'] * N
		count = maxx - 2 * N
		i = 0
		j = N - 1
		while count > 0:
			if d[0] - 2 > count:
				arr[j] = getsmaller(d, count + 2)
				count = 0
				j -= 1
			else:
				arr[i] = '0'
				count -= 4
				i += 1
		return ''.join(arr)


class Solution:

	def sevenSegments(self, S, N):
		dic = {'0': 6, '1': 2, '2': 5, '3': 5, '4': 4, '5': 5, '6': 6, '7': 3, '8': 7, '9': 5}
		count = 0
		for i in range(N):
			count += dic[S[i]]
		res = []
		for i in range(N):
			res.append('1')
			count -= 2
		for j in range(N):
			if N == 1:
				res[j] = S[0]
			elif count == 4:
				res[j] = '0'
				break
			elif count > 4:
				res[j] = '0'
				count -= 4
			elif count < 4:
				if count == 3:
					res[-1] = '2'
				elif count == 2:
					res[-1] = '4'
				elif count == 1:
					res[-1] = '7'
		return ''.join(res)


class Solution:

	def sevenSegments(self, S, n):
		mp = {0: 6, 1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 5}
		total = 0
		for i in S:
			total += mp[int(i)]
		ans = ''
		min = n * 2
		max = n * 7
		for i in range(0, n):
			min -= 2
			max -= 7
			if i == n - 1:
				for j in range(0, 10):
					if total == mp[j]:
						ans += str(j)
						break
				break
			for j in range(0, 10):
				if total - mp[j] <= max and total - mp[j] >= min:
					ans += str(j)
					total -= mp[j]
					break
		return ans


class Solution:

	def sevenSegments(self, S, N):
		l = [6, 2, 5, 5, 4, 5, 6, 3, 7, 5]
		sum = 0
		c = 0
		for i in S:
			sum += l[int(i)]
		op = [2] * N
		ans = ['1'] * N
		sum -= 2 * N
		i = 0
		while sum >= 4:
			sum -= 4
			op[i] = 6
			ans[i] = '0'
			i += 1
		i = N - 1
		while i >= 0 and sum:
			if sum > 7 - op[i]:
				sum -= 7 - op[i]
				op[i] = 7
				ans[i] = '7'
			else:
				op[i] += sum
				if op[i] == 4:
					ans[i] = '4'
				elif op[i] == 5:
					ans[i] = '2'
				elif op[i] == 3:
					ans[i] = '7'
				elif op[i] == 6:
					ans[i] = '6'
				elif op[i] == 7:
					ans[i] = '8'
				elif op[i] == 2:
					ans[i] = '1'
				sum = 0
			i = i - 1
		return ''.join(ans)


class Solution:

	def sevenSegments(self, s, n):
		d = {'0': 6, '1': 2, '2': 5, '3': 5, '4': 4, '5': 5, '6': 6, '7': 3, '8': 7, '9': 5}
		c = 0
		k = ''
		for i in s:
			c += d[i]
		l = [2] * N
		i = 0
		c -= 2 * N
		while c >= 4:
			l[i] += 4
			c -= 4
			i += 1
		j = N - 1
		while c > 0 and j >= 0:
			a = 7 - l[j]
			l[j] += min(a, c)
			c -= min(a, c)
			j -= 1
		for i in range(N):
			if l[i] == 6:
				k += '0'
			elif l[i] == 2:
				k += '1'
			elif l[i] == 5:
				k += '2'
			elif l[i] == 4:
				k += '4'
			elif l[i] == 7:
				k += '8'
			elif l[i] == 3:
				k += '7'
		return k


class Solution:

	def sevenSegments(self, S, N):
		segments = [6, 2, 5, 5, 4, 5, 6, 3, 7, 5]
		d = {2: [1], 3: [7], 4: [4], 5: [2, 3, 5, 9], 6: [0, 6], 7: [8]}
		totalSegments = 0
		segmentsUsed = 0
		for i in range(N):
			totalSegments += segments[int(S[i])]
			S = S[:i] + '1' + S[i + 1:]
			segmentsUsed += 2
		segmentsRemaining = totalSegments - segmentsUsed
		for i in range(N):
			if segmentsRemaining < 4:
				break
			S = S[:i] + '0' + S[i + 1:]
			segmentsRemaining -= 4
		if segmentsRemaining > 0:
			s = min(d[segmentsRemaining + segments[int(S[N - 1])]])
			S = S[:N - 1] + str(s)
		return S


class Solution:

	def sevenSegments(self, S, N):
		h = [6, 2, 5, 5, 4, 5, 6, 3, 7, 5]
		tl = 0
		for i in range(N):
			tl += h[int(S[i])]
		ans = ''
		for i in range(N):
			for j in range(10):
				cn = tl - h[j]
				if cn >= 2 * (N - 1 - i) and cn <= 7 * (N - i - 1):
					ans += str(j)
					tl = cn
					break
		return ans


import sys
from collections import OrderedDict
sys.setrecursionlimit(10 ** 6)

class Solution:

	def recur(self, i, s, total, dic, N, val, count):
		if val == total and count == N:
			return True
		if (N - count) * 2 > total - val or total - val < 2 or count >= N:
			return False
		if total - val >= dic[s[i]]:
			value = divmod(total - val, s[i])
			dic[s[i]] += value[0]
			val += value[0] * s[i]
			count += value[0]
			while dic[s[i]] > 0:
				if self.recur(i + 1, s, total, dic, N, val, count):
					return True
				dic[s[i]] -= 1
				val -= s[i]
				count -= 1
		if self.recur(i + 1, s, total, dic, N, val, count):
			return True
		return False

	def sevenSegments(self, S, N):
		dic = {'0': 6, '1': 2, '2': 5, '3': 5, '4': 4, '5': 5, '6': 6, '7': 3, '8': 7, '9': 5}
		val_dic = {6: '0', 2: '1', 5: '2', 4: '4', 3: '7', 7: '8'}
		s = [6, 2, 5, 4, 3, 7]
		a = OrderedDict()
		total = 0
		for i in range(N):
			total += dic[S[i]]
		if N == 1:
			return val_dic[total]
		for i in s:
			a[i] = 0
		val = total // 6
		while val > 0:
			if self.recur(1, s, total, a, N, val * 6, val):
				a[6] = val
				break
			val -= 1
		(arr, ans) = ([], '')
		for i in a:
			if a[i] > 0:
				arr += [i] * a[i]
		for i in range(len(arr)):
			ans += val_dic[arr[i]]
		return ans


class Solution:

	def sevenSegments(self, S, N):
		if N == 1:
			return S
		segments = [6, 2, 5, 5, 4, 5, 6, 3, 7, 5]
		available_segments = 0
		for ele in S:
			available_segments += segments[int(ele)]
		z = int(available_segments / 6)
		N -= z
		available_segments -= z * 6
		while available_segments < N * 2:
			available_segments += 6
			z -= 1
			N += 1
		available_segments -= N * 2
		if available_segments != 0:
			for i in range(len(segments)):
				if segments[i] == available_segments + 2:
					return '{}{}{}'.format('0' * z, '1' * (N - 1), i)
		return '{}{}'.format('0' * z, '1' * N)


class Solution:

	def sevenSegments(self, s, n):
		d = {'0': 6, '1': 2, '2': 5, '3': 5, '4': 4, '5': 5, '6': 6, '7': 3, '8': 7, '9': 5}
		sum = 0
		for i in s:
			sum += d[i]
		sum = sum - (n << 1)
		k = sum >> 2
		if k == n:
			if k << 2 == sum:
				return '0' * n
			elif n == sum - (k << 2):
				return '8' * n
			else:
				return '0' * (n - sum % n) + '8' * (sum % n)
		elif sum % 4 == 0:
			return '0' * k + '1' * (n - k)
		elif sum % 4 == 1:
			return '0' * k + '1' * (n - k - 1) + '7'
		elif sum % 4 == 2:
			return '0' * k + '1' * (n - k - 1) + '4'
		elif sum % 4 == 3:
			return '0' * k + '1' * (n - k - 1) + '2'


class Solution:

	def sevenSegments(self, S, N):
		d = {'0': 6, '1': 2, '2': 5, '3': 5, '4': 4, '5': 5, '6': 6, '7': 3, '8': 7, '9': 5}
		if S == '8':
			return S
		segments = -2 * N
		for x in S:
			segments += d[x]
		zeros = '0' * (segments // 4)
		segments %= 4
		out = ''
		x = 2
		while segments:
			out += segments // (d[str(x)] - 2) * str(x)
			segments %= d[str(x)] - 2
			x += 1
		res = zeros + '1' * (N - len(zeros) - len(out)) + out
		return res


class Solution:

	def sevenSegments(self, S, N):
		segDict = {'0': 6, '1': 2, '2': 5, '3': 5, '4': 4, '5': 5, '6': 6, '7': 3, '8': 7, '9': 5}
		if len(S) == 1:
			return S
		iniSum = sum([segDict[i] for i in S])
		iniSum -= N * 2
		left = ''
		right = ''
		left = str(left).zfill(iniSum // 4)
		iniSum %= 4
		if iniSum == 3:
			right = '2'
		elif iniSum == 2:
			right = '4'
		elif iniSum == 1:
			right = '7'
		return left + (N - len(left) - len(right)) * '1' + right


m = [6, 2, 5, 5, 4, 5, 6, 3, 7, 5]

class Solution:

	def sevenSegments(self, S, N):
		segs = sum((m[int(e)] for e in S[:N]))
		ans = ''
		while N > 0:
			N -= 1
			low = N * 2
			high = N * 7
			for digit in [0, 1, 2, 4, 7, 8]:
				left = segs - m[digit]
				if left >= low and left <= high:
					ans += str(digit)
					segs = left
					break
		return ans


class Solution:

	def sevenSegments(self, S, N):
		segments = {0: 6, 1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 5}
		c = 0
		for i in S:
			c += segments[int(i)]
		ans = []
		for i in range(N):
			ans.append('1')
			c -= 2
		for j in range(N):
			if c == 4:
				ans[j] = '0'
				break
			elif c > 4:
				ans[j] = '0'
				c -= 4
			elif c < 4:
				if c == 3:
					ans[-1] = '2'
				elif c == 2:
					ans[-1] = '4'
				elif c == 1:
					ans[-1] = '7'
		if c > 0:
			k = N - 1
			while c and k >= 0:
				l = segments[int(ans[k])]
				n = l + 1
				if str(n) == '7':
					ans[k] = '8'
				c -= 1
				N -= 1
		return ''.join(ans)


class Solution:

	def sevenSegments(self, S, N):
		arr = [6, 2, 5, 5, 4, 5, 6, 3, 7, 5]
		sumi = 0
		a = [6, 2, 5, 5, 4, 5, 6, 3, 7, 5]
		for i in range(N):
			sumi += a[int(S[i])]
		i = N
		ans = ''
		while i > 0:
			for j in range(10):
				if sumi - a[j] >= 2 * (i - 1) and sumi - a[j] <= 7 * (i - 1):
					ans += str(j)
					sumi -= a[j]
					break
			i -= 1
		return ans


from collections import OrderedDict

class Solution:

	def sevenSegments(self, S, N):
		segments = [6, 2, 5, 5, 4, 5, 6, 3, 7, 5]
		nums = {2: [1], 3: [7], 4: [4], 5: [2, 3, 5, 9], 6: [0, 6], 7: [8]}
		s = set(S)
		if s == {'0'} or s == {'8'} or N == 1:
			return S
		if s == {'0', '1'}:
			x = S.count('0')
			return '0' * x + '1' * (N - x)
		segs = 0
		for i in S:
			segs += segments[int(i)]
		zeros = (segs - 2 * N) // 4
		remainder = (segs - 2 * N) % 4
		res = ['0'] * zeros
		remaining = []
		index = 0
		while index < N - zeros and remainder > 0:
			for i in range(7, 1, -1):
				if remainder >= i - 2:
					index += 1
					remainder -= i
					remaining.append(str(nums[i][0]))
					break
		return ''.join(res + ['1'] * (N - zeros - index) + sorted(remaining))


class Solution:

	def sevenSegments(self, s, n):
		hm = [6, 2, 5, 5, 4, 5, 6, 3, 7, 5]
		seg = 0
		for x in s[:n]:
			seg += hm[int(x)]
		ans = ''
		for x in range(n - 1):
			if seg >= (n - x) * 6:
				ans += '8'
				seg -= 7
			elif seg - 6 >= (n - x - 1) * 2:
				ans += '0'
				seg -= 6
			else:
				ans += '1'
				seg -= 2
		if seg == 2:
			ans += '1'
		elif seg == 3:
			ans += '7'
		elif seg == 4:
			ans += '4'
		elif seg == 5:
			ans += '2'
		elif seg == 7:
			ans += '8'
		return ans


class Solution:

	def sevenSegments(self, S, N):
		seg = [6, 2, 5, 5, 4, 5, 6, 3, 7, 5]
		count = sum((seg[int(ch)] for ch in S[:N]))
		ans = ''
		lower = 2 * N
		upper = 7 * N
		for _ in range(N):
			lower -= 2
			upper -= 7
			for i in [0, 1, 2, 4, 7, 8]:
				remain = count - seg[i]
				if remain >= lower and remain <= upper:
					ans += str(i)
					count = remain
					break
		return ans


class Solution:

	def sevenSegments(self, S, N):
		S = S[:N]
		arr = [6, 2, 5, 5, 4, 5, 6, 3, 7, 5]
		total_seg = 0
		for i in S:
			total_seg += arr[int(i)]
		diff = total_seg - 6 * N
		val1 = [4, 3, 2, 1]
		val2 = [1, 7, 4, 2]
		if diff == 0:
			return '0' * N
		if diff < 0:
			diff = abs(diff)
			res = ''
			i = 0
			while diff != 0:
				if diff >= val1[i]:
					diff -= val1[i]
					res += str(val2[i])
				else:
					i += 1
			return res.zfill(N)
		if diff > 0:
			res = '8' * diff
			return res.zfill(N)


class Solution:

	def sevenSegments(self, S, N):
		seg = [6, 2, 5, 5, 4, 5, 6, 3, 7, 5]
		ans = [2] * N
		total = 0
		for i in range(N):
			total += seg[int(S[i])]
		total = total - 2 * N
		i = 0
		while total >= 4 and i < N:
			total -= 4
			ans[i] += 4
			i += 1
		i = N - 1
		while total > 0 and i >= 0:
			req = 7 - ans[i]
			ans[i] += min(req, total)
			total -= min(req, total)
			i -= 1
		for i in range(N):
			if ans[i] == 6:
				ans[i] = 0
			elif ans[i] == 5:
				ans[i] = 2
			elif ans[i] == 4:
				ans[i] = 4
			elif ans[i] == 3:
				ans[i] = 7
			elif ans[i] == 7:
				ans[i] = 8
			else:
				ans[i] = 1
		result = ''
		for i in range(N):
			result += str(ans[i])
		return result


class Solution:

	def sevenSegments(self, S, N):
		segs = [6, 2, 5, 5, 4, 5, 6, 3, 7, 5]
		sum = 0
		for x in range(N):
			sum += segs[int(S[x])]
		sum -= N * 2
		left = sum // 4 * '0'
		sum %= 4
		right = ''
		if sum == 3:
			right = '2'
		elif sum == 2:
			right = '4'
		elif sum == 1:
			right = '7'
		return left + (N - len(left) - len(right)) * '1' + right


class Solution:

	def sevenSegments(self, S, N):
		segments = [6, 2, 5, 5, 4, 5, 6, 3, 7, 5]
		d1 = {6: '0', 2: '1', 5: '2', 3: '7', 4: '4', 7: '8'}
		seg = 0
		for i in range(N):
			seg += segments[int(S[i])]
		seg = seg - N * 2
		res = ['1'] * N
		i = 0
		while seg >= 4 and i < N:
			res[i] = '0'
			seg -= 4
			i += 1
		j = N - 1
		while seg > 0 and j >= 0:
			r = 7 - segments[int(res[j])]
			res[j] = d1[min(seg, r) + segments[int(res[j])]]
			seg -= r
			j -= 1
		return ''.join(res)


class Solution:

	def sevenSegments(self, S, N):
		seg = [6, 2, 5, 5, 4, 5, 6, 3, 7, 5]
		count = sum((seg[int(ch)] for ch in S[:N]))
		ans = ''
		(l, u) = (2 * N, 7 * N)
		for _ in range(N):
			l -= 2
			u -= 7
			for i in [0, 1, 2, 4, 7, 8]:
				r = count - seg[i]
				if r >= l and r <= u:
					ans += str(i)
					count = r
					break
		return ans


from functools import reduce

class Solution:

	def sevenSegments(self, S, N):
		S = S[:N]
		sc = [6, 2, 5, 5, 4, 5, 6, 3, 7, 5]
		tot = reduce(lambda t, x: t + sc[int(x)], S, 0)
		res = ''
		l = N * 2
		u = N * 7
		for _ in range(N):
			l -= 2
			u -= 7
			for k in [0, 1, 2, 4, 7, 8]:
				diff = tot - sc[k]
				if diff <= u and diff >= l:
					res += str(k)
					tot = diff
					break
		return res


class Solution:

	def sevenSegments(self, S, N):
		segments = [6, 2, 5, 5, 4, 5, 6, 3, 7, 5]
		total = 0
		for i in range(N):
			total += segments[int(S[i])]
		output = ['1'] * N
		total -= 2 * N
		for i in range(N):
			if total - 4 >= 0:
				total -= 4
				output[i] = '0'
			else:
				break
		i = N - 1
		while total > 0:
			if total - 7 >= 0:
				output[i] = '8'
				total -= 7
			else:
				for j in range(9):
					if segments[j] == total + 2:
						output[i] = str(j)
						total = 0
						break
			i -= 1
		return ''.join(output)


class Solution:

	def sevenSegments(self, S, N):
		seg = [6, 2, 5, 5, 4, 5, 6, 3, 7, 5]
		c = 0
		for s in range(N):
			c += seg[int(S[s])]
		res = ['0' for _ in range(N)]
		j = N - 1
		sc = N * seg[0]
		while sc - c > 0 and j > 0:
			res[j] = '1'
			sc -= 4
			j -= 1
		if c - sc == 1:
			res[-1] = '7'
		elif c - sc == 2:
			res[-1] = '4'
		elif c - sc == 3:
			res[-1] = '2'
		return ''.join(res)


class Solution:

	def sevenSegments(self, s, n):
		a = [6, 2, 5, 5, 4, 5, 6, 3, 7, 5]
		sum_ = 0
		for i in range(n):
			sum_ += a[ord(s[i]) - 48]
		ans = [0 for _ in range(n)]
		for i in range(n):
			ans[i] = 2
			sum_ -= 2
		j = 0
		while sum_ >= 4 and j < n:
			ans[j] = 6
			sum_ += 2
			sum_ -= 6
			j += 1
		ans[n - 1] += sum_
		res = ''
		for i in ans:
			if i == 6:
				res += '0'
			elif i == 2:
				res += '1'
			elif i == 3:
				res += '7'
			elif i == 4:
				res += '4'
			elif i == 5:
				res += '2'
			else:
				res += '8'
		return res


class Solution:

	def sevenSegments(self, s, N):
		s = s[:N]
		seg = [6, 2, 5, 5, 4, 5, 6, 3, 7, 5]
		c = 0
		for i in s:
			c += seg[int(i)]
		x = ''
		for i in range(N - 1, -1, -1):
			for j in range(0, 10):
				if c - seg[j] >= 2 * i and c - seg[j] <= 7 * i:
					x = x + str(j)
					c = c - seg[j]
					break
		return x


class Solution:

	def solve(self, target, rem):
		if target >= 0 and rem >= 0 and (2 * rem <= target) and (7 * rem >= target):
			return True
		return False

	def sevenSegments(self, S, N):
		l = [6, 2, 5, 5, 4, 5, 6, 3, 7, 5]
		count = 0
		for i in range(N):
			count += l[ord(S[i]) - 48]
		ans = ''
		for i in range(1, N + 1):
			for j in range(10):
				if self.solve(count - l[j], N - i):
					count -= l[j]
					ans += str(j)
					break
		return ans


class Solution:

	def sevenSegments(self, S, N):
		mydict = {'0': 6, '1': 2, '2': 5, '3': 5, '4': 4, '5': 5, '6': 6, '7': 3, '8': 7, '9': 5}
		segs = 0
		for i in range(N):
			segs += mydict[S[i]]
		res = ''
		for i in range(N - 1, -1, -1):
			for j in range(10):
				if 2 * i <= segs - mydict[str(j)] <= 7 * i:
					res += str(j)
					segs -= mydict[str(j)]
					break
		return res


class Solution:

	def sevenSegments(self, string, n):
		hm = [6, 2, 5, 5, 4, 5, 6, 3, 7, 5]
		string = string[:n]
		total = 0
		for char in string:
			digit = int(char)
			total += hm[digit]
		ans = ''
		j = 1
		while j < n and total - 6 >= 2 * (n - j):
			ans += '0'
			total -= 6
			j += 1
		while j <= n and total > 0:
			total -= 2
			if j == n and total != 0:
				total += 2
				if total == 5:
					ans += '2'
				elif total == 4:
					ans += '4'
				elif total == 3:
					ans += '7'
				elif total == 7:
					ans += '8'
				break
			else:
				ans += '1'
				j += 1
		return ans


class Solution:

	def sevenSegments(self, s, n):
		f = [0] * 10
		for c in s[:n]:
			f[int(c)] += 1
		f[0] += f[6]
		f[6] = 0
		f[2] += f[3] + f[5] + f[9]
		(f[3], f[5], f[9]) = (0, 0, 0)
		for z in range(3):
			for (a, b, c, d) in [[2, 8, 0, 0], [2, 7, 0, 1], [4, 4, 0, 1], [4, 8, 0, 2], [2, 2, 0, 4], [7, 8, 0, 4], [1, 8, 0, 7], [2, 4, 0, 7], [7, 4, 1, 2], [7, 7, 1, 4]]:
				m = min(f[a], f[b])
				if a == b:
					m = f[a] // 2
				f[a] -= m
				f[b] -= m
				f[c] += m
				f[d] += m
		return ''.join([str(i) * f[i] for i in range(10)])


class Solution:

	def sevenSegments(self, S, N):
		num_to_segs = {'0': 6, '1': 2, '2': 5, '3': 5, '4': 4, '5': 5, '6': 6, '7': 3, '8': 7, '9': 5}
		segs_to_num = {2: '1', 3: '7', 4: '4', 5: '2', 6: '0', 7: '8'}
		total_segs = sum([num_to_segs[S[i]] for i in range(N)])
		result = ['1'] * N
		remaining_segs = total_segs - 2 * N
		position = 0
		while remaining_segs > 3 and position < N:
			result[position] = '0'
			position += 1
			remaining_segs -= 4
		position = N
		while remaining_segs and position:
			position -= 1
			if result[position] == '0':
				result[position] = '8'
				remaining_segs -= 1
			elif remaining_segs + 2 in segs_to_num:
				result[position] = segs_to_num[remaining_segs + 2]
				break
		return ''.join(result)


class Solution:

	def sevenSegments(self, S, N):
		charArr = list(S)
		seg = [6, 2, 5, 5, 4, 5, 6, 3, 7, 5]
		upper = 7 * N
		lower = 2 * N
		count_seg = sum((seg[int(charArr[i])] for i in range(N)))
		count_zeros = int(count_seg / 6)
		remaining_seg = count_seg % 6
		new_str = '0' * count_zeros
		min_list = [0, 1, 2, 4, 5, 7, 8]
		c = 0
		ans = ''
		for i in range(N):
			lower -= 2
			upper -= 7
			for i in min_list:
				rem = count_seg - seg[i]
				if rem >= lower and rem <= upper:
					ans += str(i)
					count_seg = rem
					break
		return ans


class Solution:

	def sevenSegments(self, s, n):
		a = [6, 2, 5, 5, 4, 5, 6, 3, 7, 5]
		d = {2: 1, 3: 7, 4: 4, 5: 2, 6: 0, 7: 8}
		priority = [6, 2, 5, 4, 3, 7]
		count_segment = 0
		for i in range(n):
			count_segment += a[int(s[i])]
		ans = ''
		i = 0
		ip = 0
		while count_segment != 0 and i < n:
			remaining_places = n - i - 1
			x = count_segment - priority[ip]
			if i == n - 1:
				ans += str(d[count_segment])
				i += 1
				continue
			elif x / remaining_places >= 2 and x >= 0:
				ans += str(d[priority[ip]])
			else:
				while x / remaining_places < 2:
					ip += 1
					x = count_segment - priority[ip]
				ans += str(d[priority[ip]])
			count_segment -= priority[ip]
			i += 1
		return ans


class Solution:

	def sevenSegments(self, s, n):
		m = [6, 2, 5, 5, 4, 5, 6, 3, 7, 5]
		c = sum((m[int(s[i])] for i in range(n)))
		a = [0] * 10
		if c > 6 * n:
			(a[0], a[8]) = (n - (c - 6 * n), c - 6 * n)
		else:
			c -= 2 * n
			if c % 4 == 0:
				(a[0], a[1]) = (c // 4, n - c // 4)
			elif c % 4 == 1:
				(a[0], a[1], a[7]) = (c // 4, n - c // 4 - 1, 1)
			elif c % 4 == 2:
				(a[0], a[1], a[4]) = (c // 4, n - c // 4 - 1, 1)
			elif c % 4 == 3:
				(a[0], a[1], a[2]) = (c // 4, n - c // 4 - 1, 1)
		return ''.join((str(i) * x for (i, x) in enumerate(a)))


class Solution:

	def sevenSegments(self, S, N):
		s = [6, 2, 5, 5, 4, 5, 6, 3, 7, 5]
		ans = ''
		sum1 = 0
		for i in range(N):
			k = int(S[i])
			sum1 += s[k]
		a = []
		for i in range(N):
			a.append(2)
			sum1 -= 2
		i = 0
		while sum1 >= 4 and i < N:
			sum1 += 2
			a[i] = 6
			sum1 -= 6
			i += 1
		a[N - 1] += sum1
		for i in range(N):
			if a[i] == 6:
				ans += '0'
			elif a[i] == 2:
				ans += '1'
			elif a[i] == 3:
				ans += '7'
			elif a[i] == 4:
				ans += '4'
			else:
				ans += '2'
		return ans


class Solution:

	def sevenSegments(self, S, N):
		d = [6, 2, 5, 5, 4, 5, 6, 3, 7, 5]
		sm = 0
		S = S[:N]
		for i in S:
			sm += d[int(i)]
		sm -= 2 * N
		a = [1 for i in range(N)]
		i = 0
		while sm >= 4 and i < N:
			a[i] = 0
			i += 1
			sm -= 4
		i = N - 1
		while sm > 0 and i > -1:
			if sm >= 5:
				a[i] = 8
				i -= 1
				sm -= 5
			elif sm >= 4:
				a[i] = 6
				i -= 1
				sm -= 4
			elif sm >= 3:
				a[i] = 2
				i -= 1
				sm -= 3
			elif sm >= 2:
				a[i] = 4
				i -= 1
				sm -= 2
			elif sm >= 1:
				a[i] = 7
				i -= 1
				sm -= 1
		return ''.join([str(x) for x in a])


class Solution:

	def sevenSegments(self, S, N):
		dic = {'0': 6, '1': 2, '2': 5, '3': 5, '4': 4, '5': 5, '6': 6, '7': 3, '8': 7, '9': 5}
		total = sum((dic[i] for i in S[:N]))
		ans = ''
		for bit in range(N):
			(left, right) = (2 * (N - bit - 1), 7 * (N - bit - 1))
			digit = 0
			rem = total - dic[str(digit)]
			while not (left <= rem and right >= rem):
				digit += 1
				rem = total - dic[str(digit)]
			ans += str(digit)
			total = total - dic[str(digit)]
		return ans


class Solution:

	def sevenSegments(self, S, N):
		seg = [6, 2, 5, 5, 4, 5, 6, 3, 7, 5]
		count = sum((seg[int(ch)] for ch in S[:N]))
		ans = ''
		left = 2 * N
		right = 7 * N
		for _ in range(N):
			left -= 2
			right -= 7
			for i in range(10):
				remain = count - seg[i]
				if remain >= left and remain <= right:
					ans += str(i)
					count = remain
					break
		return ans


class Solution:

	def sevenSegments(self, S, N):
		digits = [6, 2, 5, 5, 4, 5, 6, 3, 7, 5]
		_min_digits = min(digits)
		total = 0
		for i in range(N):
			total += digits[int(S[i])]
		res = []
		for i in range(N - 1, -1, -1):
			for j in range(10):
				if total - digits[j] >= 2 * i and total - digits[j] <= 7 * i:
					res.append(str(j))
					total -= digits[j]
					break
		return ''.join(res)


class Solution:

	def sevenSegments(self, S, N):
		seg = [6, 2, 5, 5, 4, 5, 6, 3, 7, 5]
		count = sum((seg[int(ch)] for ch in S[:N]))
		ans = ''
		for i in range(N, 0, -1):
			if i == 1:
				if count == 2:
					ans += '1'
				elif count == 3:
					ans += '7'
				elif count == 4:
					ans += '4'
				else:
					ans += '2'
			elif count <= i * 2 + 3:
				ans += '1'
				count -= 2
			elif count <= i * 6:
				ans += '0'
				count -= 6
			else:
				ans += '8'
				count -= 7
		return ans


class Solution:

	def sevenSegments(self, S, N):
		S = S[:N]
		segments = {'0': 6, '1': 2, '2': 5, '3': 5, '4': 4, '5': 5, '6': 6, '7': 3, '8': 7, '9': 5}
		rem = sum((segments[c] for c in S))
		res = []
		for i in range(N - 1, -1, -1):
			for c in sorted(segments):
				if 2 * i <= rem - segments[c] <= 7 * i:
					rem -= segments[c]
					res += c
					break
		return ''.join(res)