A number is called a Sparse number if its binary form doesn’t have any two adjacent 1s. Ex. 9 = 1001, 10 = 1010 but 11 is not a Sparse number as 11 = 1011 which has last 1s as adjacent 1s. Find the first Sparse number coming after numbers given in column A.
📌 Challenge Details and Links
ExcelBI Excel Challenge Number: 512
Challenge Difficulty: ⭐️⭐️⭐️
📥Download Sample File
📥Link to the solutions on LinkedIn
Solving the challenge of Find Next Sparse Number with Power Query
Power Query solution 1 for Find Next Sparse Number, proposed by Bo Rydobon 🇹🇭:
let
Source = Excel.CurrentWorkbook(){[Name = "Table1"]}[Content],
Sp = (b) =>
let
f = Text.PositionOf(b, "11")
in
if f = - 1 then
b
else
(
if f = 0 then
"1" & Text.Repeat("0", Text.Length(b) - f)
else
@Sp(Text.Start(b, f - 1) & "1" & Text.Repeat("0", Text.Length(b) - f))
),
Ans = Table.AddColumn(
Source,
"Ans",
each
let
b = Text.Combine(
List.Reverse(
List.Transform(
{0 .. Number.RoundDown(Number.Log([Number], 2))},
(D) => Text.From(Number.Mod(Number.RoundDown([Number] / Number.Power(2, D)), 2))
)
)
),
B = Sp(b),
l = Text.Length(B)
in
List.Sum(
List.Transform(
{0 .. l - 1},
(n) => Number.From(Text.ToList(B){n}) * Number.Power(2, l - n - 1)
)
)
)
in
AnsPower Query solution 2 for Find Next Sparse Number, proposed by Alejandro Simón 🇵🇦 🇪🇸:
let
Source = Excel.CurrentWorkbook(){[Name = "Table1"]}[Content],
Filter = Table.SelectRows(Source, each ([Number] <> 94734028 and [Number] <> 548926753)),
Sol = Table.AddColumn(
Filter,
"Answer",
each List.Last(
List.Generate(
() => [x = [Number], y = false],
each [y] = false,
each [
x = [x] + 1,
y =
let
a = Number.RoundDown(Number.Log([x], 2)),
b = List.Reverse({0 .. a}),
c = List.Transform(
b,
(q) => Number.Mod(Number.RoundDown([x] / Number.Power(2, q)), 2)
),
d = List.AllTrue(
List.Transform(
{1 .. List.Count(c) - 1},
each if c{_} = 1 and c{_ - 1} = 1 then false else true
)
)
in
d
],
each [x]
)
)
)
in
SolSolving the challenge of Find Next Sparse Number with Excel
Excel solution 1 for Find Next Sparse Number, proposed by Bo Rydobon 🇹🇭:
=MAP(A2:A10,
LAMBDA(n,
LET(b,
BASE(
n,
2
),
c,
REGEXREPLACE(
b,
".?(10)*11.*",
),
DECIMAL(c&1&REPT(0,
LEN(
b
)-LEN(
c
)-(c>"")),
2))))Excel solution 2 for Find Next Sparse Number, proposed by Bo Rydobon 🇹🇭:
=MAP(
A2:A10,
LAMBDA(
n,
LET(
b,
BASE(
n,
2
),
f,
MIN(
IFERROR(
FIND(
REPT(
10,
SEQUENCE(
9
)-1
)&11,
b
),
99
)
)-1,
DECIMAL(
IFERROR(
LEFT(
b,
f-1
),
""
)&1&REPT(
0,
LEN(
b
)-f
),
2
)
)
)
)Excel solution 3 for Find Next Sparse Number, proposed by Bo Rydobon 🇹🇭:
=LET(
r,
LAMBDA(
r,
b,
LET(
f,
FIND(
11,
b
),
IF(
ISERR(
f
),
DECIMAL(
b,
2
),
r(
r,
IFERROR(
LEFT(
b,
f-2
),
""
)&1&REPT(
0,
LEN(
b
)-f+1
)
)
)
)
),
MAP(
A2:A10,
LAMBDA(
n,
r(
r,
BASE(
n+1,
2
)
)
)
)
)Excel solution 4 for Find Next Sparse Number, proposed by Rick Rothstein:
=MAP(
A2:A10,
LAMBDA(
x,
LET(
b,
BASE(
x,
2
),
p,
LEN(
b
),
t,
TEXTBEFORE(
b,
{"11",
"1011"}
),
q,
LEN(
t
),
i,
IF(
t="",
1&REPT(
0,
p
),
LEFT(
t,
q-1
)&1&REPT(
0,
p-q
)
),
r,
LEN(
i
),
SUM(
MID(
i,
SEQUENCE(
r
),
1
)*TAKE(
SORT(
2^SEQUENCE(
31,
,
0
),
,
-1
),
-r
)
)
)
)
)Excel solution 5 for Find Next Sparse Number, proposed by John V.:
=LET(
r,
LAMBDA(
r,
n,
LET(
p,
FIND(
11,
n
),
IF(
ISERR(
p
),
n,
r(
r,
LEFT(
n,
MAX(
,
p-2
)
)&1&REPT(
0,
1+LEN(
n
)-p
)
)
)
)
),
MAP(
A2:A10,
LAMBDA(
x,
DECIMAL(
r(
r,
BASE(
x,
2
)
),
2
)
)
)
)Excel solution 6 for Find Next Sparse Number, proposed by محمد حلمي:
=LET(
b,
BASE(
A2:A10,
2
),
j,
LEN(
b
),
e,
FIND(
11,
b
),
i,
LEFT(
b,
e-2
),
DECIMAL(
IF(
e<4,
1&
REPT(
0,
j
),
IF(
RIGHT(
i
)="1",
i&0,
i&1
)&REPT(
0,
j-e+1
)
),
2
)
)Excel solution 7 for Find Next Sparse Number, proposed by محمد حلمي:
=MAP(A2:A3,LAMBDA(a,LET(e,SEQUENCE(20,,a+1),
XLOOKUP(TRUE,ISERR( FIND(11,DEC2BIN(+e))),e))))Excel solution 8 for Find Next Sparse Number, proposed by Julian Poeltl:
=MAP(
A2:A10,
LAMBDA(
A,
LET(
B,
BASE(
A,
2
),
L,
LEN(
B
),
M,
MIN(
IFERROR(
SEARCH(
{11,
101},
B
),
L
)
),
DECIMAL(
LEFT(
B,
M-IF(
M=1,
1,
2
)
)&1&REPT(
0,
L-M+1
),
2
)
)
)
)Excel solution 9 for Find Next Sparse Number, proposed by Timothée BLIOT:
=LET(A,
BASE(
A2:A10,
2
),
B,
MAP(
A,
LAMBDA(
x,
MIN(
IFERROR(
FIND(
{"11",
"1011"},
x
),
""
)
)
)
),
MAP(IFERROR(
MID(
A,
1,
B-2
),
""
)&10&REPT(
0,
LEN(
A
)-B
),
LAMBDA( x,
SUM((2^(LEN(
x
)-SEQUENCE(
LEN(
x
)
)))*MID(
x,
SEQUENCE(
LEN(
x
)
),
1
)))))Excel solution 10 for Find Next Sparse Number, proposed by LEONARD OCHEA 🇷🇴:
=MAP(
A2:A10,
LAMBDA(
a,
LET(
b,
BASE(
a,
2
),
F,
LAMBDA(
F,
x,
LET(
i,
FIND(
11,
x
),
n,
IFERROR(
LEFT(
x,
i-2
),
""
)&1&REPT(
0,
LEN(
x
)-i+1
),
IF(
ISNUMBER(
FIND(
11,
n
)
),
F(
F,
n
),
n
)
)
),
DECIMAL(
F(
F,
b
),
2
)
)
)
)Solving the challenge of Find Next Sparse Number with Python
Python solution 1 for Find Next Sparse Number, proposed by Konrad Gryczan, PhD:
import pandas as pd
path = "512 Next Sparse Number.xlsx"
input = pd.read_excel(path, usecols="A")
test = pd.read_excel(path, usecols="B")
def next_no_adjacent_ones(n):
n += 1
while True:
if '11' not in bin(n):
return n
n += 1
result = input.copy()
result['Answer Expected'] = result['Number'].apply(next_no_adjacent_ones)
print(result['Answer Expected'].equals(test['Answer Expected'])) # True
Solving the challenge of Find Next Sparse Number with Python in Excel
Python in Excel solution 1 for Find Next Sparse Number, proposed by Alejandro Campos:
def is_sparse(n):
return (n & (n >> 1)) == 0
def next_sparse(n):
while not is_sparse(n):
n += 1
return n
numbers = xl("A2:A10")[0]
next_sparse_numbers = [next_sparse(num + 1) for num in numbers]
next_sparse_numbers
Python in Excel solution 2 for Find Next Sparse Number, proposed by Abdallah Ally:
# Create a function to generate required results
def min_sparse_after_number(number):
start = number + 1
while True:
for num in range(start, start * 10):
if '11' not in bin(num):
return num
start *= 10
df = xl("A1:B10", headers=True)
# Perform data munging
df['My Answer'] = df['Number'].map(min_sparse_after_number)
df['Check'] = df['Answer Expected'] == df['My Answer']
df
Solving the challenge of Find Next Sparse Number with R
R solution 1 for Find Next Sparse Number, proposed by Konrad Gryczan, PhD:
library(tidyverse)
library(readxl)
path = "Excel/512 Next Sparse Number.xlsx"
input = read_excel(path, range = "A1:A10")
test = read_excel(path, range = "B1:B10")
next_sparse_number_fast <- function(n) {
repeat {
m <- n
k <- 0
change_required <- FALSE
while (m > 0) {
if ((m %% 4) == 3) {
change_required <- TRUE
break
}
m <- m %/% 2
k <- k + 1
}
if (!change_required) break
n <- (n %/% (2^(k + 1))) * (2^(k + 1)) + (2^(k + 1))
}
return(n)
}
result = input %>%
mutate(`Answer Expected` = map_dbl(Number, next_sparse_number_fast))
identical(result$`Answer Expected`, test$`Answer Expected`)
#> [1] TRUE
R solution 2 for Find Next Sparse Number, proposed by Konrad Gryczan, PhD:
library(tidyverse)
library(readxl)
path = "Excel/512 Next Sparse Number.xlsx"
input = read_excel(path, range = "A1:A10")
test = read_excel(path, range = "B1:B10")
is_sparse <- function(n) {
binary_n <- intToBits(n)
for (i in 2:length(binary_n)) {
if (binary_n[i] == 1 && binary_n[i - 1] == 1) {
return(FALSE)
}
}
return(TRUE)
}
detect((n + 1):(2 * n + 1), is_sparse)
}
result = input %>%
mutate(`Answer Expected` = map_dbl(Number, next_sparse_number_slow))
&&&