Given a number S, you need to check whether any permutation of the number S divisible by 8 or not. 
Example 1:
Input: S = "80"
Output: "Divisible"
Explanation: 80 is divisible by 8
Example 2
Input: S = "101"
Output: "Not divisible"
Your Task :
Complete the function isDivisible8() that receives a string S denoting the number and returns 1 if any permutation of the number is divisible by 8 or else returns 0.
Expected Time Complexity : O(lS|^{3})
Expected Space Complexity : O(1)
Constraints:
1 ≤ lS| ≤ 10^{2}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Mathematics

Starter code: #User function Template for python3



class Solution:

    def isDivisible8(self, S):

        # code here

Solutions:
class Solution:

	def isDivisible8(self, S):
		if len(S) == 1:
			return int(not int(S) % 8)
		elif len(S) == 2:
			a = S[0]
			b = S[1]
			if int(a + b) % 8 == 0 or int(b + a) % 8 == 0:
				return 1
			return 0
		for i in range(len(S)):
			for j in range(i + 1, len(S)):
				for k in range(j + 1, len(S)):
					a = S[i]
					b = S[j]
					c = S[k]
					if int(a + b + c) % 8 == 0:
						return 1
		return 0


class Solution:

	def isDivisible8(self, S):
		n = len(S)
		two_digit = [0, 8, 16, 24, 32, 40, 48, 56, 64, 72, 80, 88, 96]
		if len(S) > 2:
			for i in range(n):
				for j in range(i + 1, n):
					for k in range(j + 1, n):
						if int(S[i] + S[j] + S[k]) % 8 == 0:
							return 1
		elif int(S) in two_digit:
			return 1
		return 0


from itertools import permutations

class Solution:

	def isDivisible8(self, S):
		if len(S) >= 3:
			p = list(set(permutations(S, 3)))
		else:
			p = list(set(permutations(S)))
		p = [int(''.join(i)) for i in p]
		for num in p:
			if num % 8 == 0:
				return True
		return False


class Solution:

	def isDivisible8(self, s):
		if len(s) <= 3:
			return int(s) % 8 == 0
		counts = [0] * 10
		for j in s:
			counts[int(j)] += 1
		multiples = [['0', '0', '8']]
		c = 8
		while c + 8 < 1001:
			c += 8
			multiples.append(['0'] + list(str(c)) if len(str(c)) != 3 else list(str(c)))
		for j in multiples:
			allPresent = True
			for k in j:
				if counts[int(k)] == 0:
					allPresent = False
				counts[int(k)] -= 1
			for k in j:
				counts[int(k)] += 1
			if allPresent:
				return True
		return False


class Solution:

	def isDivisible8(self, S):
		if len(S) == 1:
			if int(S) % 8 == 0:
				return True
			return False
		if len(S) == 2:
			if int(S) % 8 == 0:
				return True
			S = S[::-1]
			if int(S) % 8 == 0:
				return True
			return False
		n = len(s)
		for i in range(n):
			for j in range(i + 1, n):
				for k in range(j + 1, n):
					t = S[i] + S[j] + S[k]
					if int(t) % 8 == 0:
						return True
		return False


class Solution:

	def solve(self, n, l):
		if l < 3:
			if int(n) % 8 == 0:
				return True
			n = n[::-1]
			if int(n) % 8 == 0:
				return True
			return False
		hash = 10 * [0]
		for i in range(0, l):
			hash[int(n[i]) - 0] += 1
		for i in range(104, 1000, 8):
			dup = i
			freq = 10 * [0]
			freq[int(dup % 10)] += 1
			dup = dup / 10
			freq[int(dup % 10)] += 1
			dup = dup / 10
			freq[int(dup % 10)] += 1
			dup = i
			if freq[int(dup % 10)] > hash[int(dup % 10)]:
				continue
			dup = dup / 10
			if freq[int(dup % 10)] > hash[int(dup % 10)]:
				continue
			dup = dup / 10
			if freq[int(dup % 10)] > hash[int(dup % 10)]:
				continue
			return True
		return False

	def isDivisible8(self, S):
		num = str(S)
		if self.solve(num, len(num)):
			return 1
		else:
			return 0