46
\$\begingroup\$

You should write a program or function that given a list of positive integers multiplies each element with the smallest positive integer possible to create a strictly increasing list.

For example if the input is

5 4 12 1 3

the multiplications will be

5*1=5 4*2=8 12*1=12 1*13=13 3*5=15

and the output will be the increasing list

5 8 12 13 15

Input

  • A list of positive integers containing at least 1 element

Output

  • A list of positive integers

Examples

9 => 9 1 2 => 1 2 2 1 => 2 3 7 3 => 7 9 1 1 1 1 => 1 2 3 4 5 4 12 1 3 => 5 8 12 13 15 3 3 3 8 16 => 3 6 9 16 32 6 5 4 3 2 1 => 6 10 12 15 16 17 9 4 6 6 5 78 12 88 => 9 12 18 24 25 78 84 88 8 9 41 5 12 3 5 6 => 8 9 41 45 48 51 55 60 15 8 12 47 22 15 4 66 72 15 3 4 => 15 16 24 47 66 75 76 132 144 150 153 156

This is code golf so the shortest program or function wins.

Fun fact: the last element of the output for the input N, N-1, ... ,1 seems to be the (N+1)th element of the sequence A007952. If you find a proof, you are welcomed to include it in your golf answer or post it as a comment.

Improve this question
\$\endgroup\$
1
  • 1
    \$\begingroup\$ has anyone made ground on that proof yet? \$\endgroup\$ Commented Feb 10, 2016 at 22:53

36 Answers 36

Reset to default
1
2
20
\$\begingroup\$

Jelly, 6 5 bytes

:‘×µ\

First Jelly answer before @Dennis wakes up and beats me. Try it online!

Explanation

: Integer division, m//n ‘ Increment, (m//n+1) × Multiply, (m//n+1)*n µ Turn the previous links into a new monadic chain \ Accumulate on the array

Thanks to @Dennis for -1 byte.

Improve this answer
\$\endgroup\$
2
  • 5
    \$\begingroup\$ :‘×µ\ saves a byte. \$\endgroup\$ Commented Feb 9, 2016 at 15:53
  • 25
    \$\begingroup\$ @Dennis Oh shit he woke up \$\endgroup\$ Commented Feb 9, 2016 at 18:29
10
\$\begingroup\$

JavaScript (ES6), 28

Edit As suggested by @Patrick Roberts, p can be a uninitialized parameter. Same byte count but avoid using a global variable

(a,p)=>a.map(n=>p=n*-~(p/n))

TEST

f=(a,p)=>a.map(n=>p=n*-~(p/n)) console.log=x=>O.textContent+=x+'\n' ;[ [[9], [ 9]], [[1, 2], [ 1, 2]], [[2, 1], [ 2, 3]], [[7, 3], [ 7, 9]], [[1, 1, 1, 1], [ 1, 2, 3, 4]], [[5, 4, 12, 1, 3], [ 5, 8, 12, 13, 15]], [[3, 3, 3, 8, 16], [ 3, 6, 9, 16, 32]], [[6, 5, 4, 3, 2, 1], [ 6, 10, 12, 15, 16, 17]], [[9, 4, 6, 6, 5, 78, 12, 88], [ 9, 12, 18, 24, 25, 78, 84, 88]], [[8, 9, 41, 5, 12, 3, 5, 6], [ 8, 9, 41, 45, 48, 51, 55, 60]], [[15, 8, 12, 47, 22, 15, 4, 66, 72, 15, 3, 4], [ 15, 16, 24, 47, 66, 75, 76, 132, 144, 150, 153, 156]] ].forEach(t=>{ var i=t[0],k=t[1],r=f(i),ok=(k+'')==(r+'') console.log(i + ' => ' + r + (ok?' OK':'FAIL expecting '+x)) })
<pre id=O></pre>

Improve this answer
\$\endgroup\$
12
  • \$\begingroup\$ I think you can save a few bytes by using modulo, just like I did in my answer. \$\endgroup\$ Commented Feb 9, 2016 at 16:31
  • \$\begingroup\$ Can't you skip the p=0? You need it to run it multiple on multiple lists but the question is just for a single list \$\endgroup\$ Commented Feb 9, 2016 at 16:34
  • 1
    \$\begingroup\$ @CharlieWynn if you don't initialize a variable you get the error for undefined variable. If by chance the variable already exists (that could easily happen in the environment of a web page), it could have any wrong value. \$\endgroup\$ Commented Feb 9, 2016 at 17:47
  • \$\begingroup\$ @edc65 sure enough, p is already defined on this page! \$\endgroup\$ Commented Feb 9, 2016 at 17:52
  • 1
    \$\begingroup\$ @PatrickRoberts thinking again, I could still avoid globals: f=a=>a.map(n=>a+=n-a%n,a=0). But it's not my algorithm (silly me) so I'll keep mine as is and upvote aross \$\endgroup\$ Commented Feb 10, 2016 at 20:19
7
\$\begingroup\$

Python 2, 67 64 bytes

First try at code-golfing, so tips are appreciated.

def m(l): for x in range(1,len(l)):l[x]*=l[x-1]/l[x]+1 print l
Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Hi, I think you're counting the line returns as 2 bytes each (using Windows?), but on this site you count each line return as a single byte. So your score is actually 65 bytes. (You can copy and paste your code into mothereff.in/byte-counter if you're not sure.) Also, you can do print l instead of return l to save another byte. Nice job! \$\endgroup\$ Commented Feb 10, 2016 at 15:52
  • \$\begingroup\$ Thanks, I didn't know about the line returns. That explains why I've always got different byte counts. And I didn't even consider, that printing is sufficient and it doesn't have to return the list. \$\endgroup\$ Commented Feb 10, 2016 at 20:34
  • \$\begingroup\$ No problem! BTW, since you mentioned that "tips are appreciated", you might be interested in browsing through codegolf.stackexchange.com/questions/54/… . Enjoy! \$\endgroup\$ Commented Feb 12, 2016 at 17:11
6
\$\begingroup\$

PHP, 55 46 42 41 bytes

Uses ISO 8859-1 encoding.

for(;$a=$argv[++$i];)echo$l+=$a-$l%$a,~ß;

Run like this (-d added for aesthetics only):

php -d error_reporting=30709 -r 'for(;$a=$argv[++$i];)echo$l+=$a-$l%$a,~ß;' 10 10 8
  • Saved 1 byte thx to Ismael Miguel.
  • Saved 8 bytes by using modulo instead of floor
  • Saved 4 bytes thx to Ismael Miguel (for instead of foreach)
  • Saved a byte by using ~ß to yield a space.
Improve this answer
\$\endgroup\$
8
  • \$\begingroup\$ I think that you can replace $a+0 with +$a. Also, you can assume that the input will never have a 0, so, you can replace your $a+0&&print with simply +$a&print. In fact, you could even do $a&print, since in PHP "0" == 0 == 0.0 == false. But it may not be needed if you just use an echo, I think. \$\endgroup\$ Commented Feb 9, 2016 at 15:56
  • \$\begingroup\$ Binary and won't work (as opposed to logical), nor will echo work in this way. Since I'm taking input from CLI, the first argument is -, which I wanna catch instead of printing a zero. Try php -r 'print_r($argv);' foo. Saved 1 byte with your first suggestion though, thx. \$\endgroup\$ Commented Feb 9, 2016 at 16:09
  • 1
    \$\begingroup\$ How about for(;$a=$argv[++$i];)echo$l+=$a-$l%$a,' ';? It is 42 bytes long and skips the first element. \$\endgroup\$ Commented Feb 9, 2016 at 16:36
  • \$\begingroup\$ Nice one, thx @IsmaelMiguel \$\endgroup\$ Commented Feb 9, 2016 at 16:44
  • \$\begingroup\$ You're welcome. If you want to be really kinky, you can replace the space with a^A, but that would spill too many warnings (warnings are ignorable). It won't change the bytecount in any way, but surelly looks different. \$\endgroup\$ Commented Feb 9, 2016 at 16:47
5
\$\begingroup\$

Haskell (30 28 25 bytes)

scanl1(\x y->y*div x y+y)

Expanded version

f :: Integral n => [n] -> [n] f xs = scanl1 increaseOnDemand xs where increaseOnDemand :: Integral n => n -> n -> n increaseOnDemand acc next = next * (1 + acc `div` next)

Explanation

scanl1 enables you to fold a list and accumulate all intermediate values into another list. It's a specialization of scanl, which has the following type:

scanl :: (acc -> elem -> acc) -> acc -> [elem] -> [acc] scanl1 :: (elem -> elem -> elem) -> [elem] -> [elem] scanl1 f (x:xs) = scanl f x xs

Therefore, all we need is a suitable function that takes two the last element of our list (acc in the expanded version) and the one we wish to process (next in the expanded version) and return a suitable number.

We can easily derive this number by dividing the accumulator through the next one and flooring the result. div takes care of that. Afterwards, we simply have to add 1 to ensure that the list is actually increasing (and that we don't end up with 0).

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ No need to give your function a name. You can also replace the ( ... ) with $ ... and I think you've counted a final newline which can be omitted: scanl1$\x y->y*div x y+y, 24 bytes. \$\endgroup\$ Commented Feb 9, 2016 at 16:30
  • \$\begingroup\$ @nimi: Really? Expressions count? That being said, I don't save any bytes with (...) vs $, since $\ gets parsed as operator and I would need a single space after $. \$\endgroup\$ Commented Feb 9, 2016 at 17:10
  • \$\begingroup\$ unnamed function are allowed by default an scanl1(...) is an unnamed function. Regarding $vs. (): you're right, my mistake. \$\endgroup\$ Commented Feb 9, 2016 at 17:11
5
\$\begingroup\$

C++, 63 60 57 bytes

void s(int*f,int*e){for(int c=*f;++f!=e;c=*f+=c/ *f**f);}

Works inplace given a range [first, last). Originally written as template variant, but that was longer:

template<class T>void s(T f,T e){for(auto c=*f;++f!=e;c=*f+=c/ *f**f);}

Extended version

template <class ForwardIterator> void sort(ForwardIterator first, ForwardIterator last){ auto previous = *first; for(++first; first != last; ++first){ auto & current = *first; current += current * (current / previous); previous = current; } }
Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Mathematica, 36 32 bytes

 #2(Floor[#1/#2]+1)&~FoldList~#&

Test

#2(Floor[#1/#2]+1)&~FoldList~#& /@ {{5, 4, 12, 1, 3}, {15, 8, 12, 47, 22, 15, 4, 66, 72, 15, 3, 4}} (* {{5, 8, 12, 13, 15}, {15, 16, 24, 47, 66, 75, 76, 132, 144, 150, 153, 156}} *)
Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Brachylog, 12 bytes

{≤.;?%0∧}ᵐ<₁

Weird enough trying to multiply each variable by a number will start at trying to multiply by 2 and not 0 or 1. This seems to work though and beats both other Brachylog implementations

Explanation

{ }ᵐ -- Map each number ≤. -- to a number greater or equal to the original .;?%0 -- and a multiple of the original ∧ -- no more constraints <₁ -- so that the list is strictly increasing

Try it online!

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

CJam, 13 bytes

q~{\_p1$/)*}*

Input as a CJam-style list. Output is linefeed separated.

Test it here.

Explanation

q~ e# Read and evaluate input. { e# Fold this block over the list (i.e. "foreach except first")... \ e# Swap with previous value. _p e# Duplicate and print previous value. 1$ e# Copy current value. / e# Integer division. )* e# Increment and multiply current value by the result. }*

The final value is left on the stack and printed automatically at the end.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Perl, 17 + 3 = 20 bytes

$p=$_*=$==1+$p/$_

Requires -p and -l flags:

$ perl -ple'$p=$_*=$==1+$p/$_' <<< $'15\n8\n12\n47\n22\n15\n4\n66\n72\n15\n3\n4' 15 16 24 47 66 75 76 132 144 150 153 156

Explanation:

# '-p' reads each line into $_ and auto print # '-l' chomp off newline on input and also inserts a new line when printing # When assigning a number to `$=` it will automatic be truncated to an integer # * Added newlines for each assignment $p= $_*= $== 1+$p/$_
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Python (3.5), 63 62 bytes

def f(a): r=[0] for i in a:r+=i*(r[-1]//i+1), return r[1:]

Test

>>> print('\n'.join([str(i)+' => '+str(f(i)) for i in [[9],[1,2],[2,1],[7,3],[1,1,1,1],[5,4,12,1,3],[3,3,3,8,16],[6,5,4,3,2,1],[9,4,6,6,5,78,12,88],[8,9,41,5,12,3,5,6],[15,8,12,47,22,15,4,66,72,15,3,4]]])) [9] => [9] [1, 2] => [1, 2] [2, 1] => [2, 3] [7, 3] => [7, 9] [1, 1, 1, 1] => [1, 2, 3, 4] [5, 4, 12, 1, 3] => [5, 8, 12, 13, 15] [3, 3, 3, 8, 16] => [3, 6, 9, 16, 32] [6, 5, 4, 3, 2, 1] => [6, 10, 12, 15, 16, 17] [9, 4, 6, 6, 5, 78, 12, 88] => [9, 12, 18, 24, 25, 78, 84, 88] [8, 9, 41, 5, 12, 3, 5, 6] => [8, 9, 41, 45, 48, 51, 55, 60] [15, 8, 12, 47, 22, 15, 4, 66, 72, 15, 3, 4] => [15, 16, 24, 47, 66, 75, 76, 132, 144, 150, 153, 156]

Previous solution

some recursive solutions but larger 

(68 bytes) f=lambda a,i=0:[i,*f(a[1:],a[0]*(i//a[0]+1))][i==0:]if a!=[]else[i] (64 bytes) f=lambda a,i=0:a>[]and[i,*f(a[1:],a[0]*(i//a[0]+1))][i<1:]or[i]
Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Also instead of r+=[…], you can use r+=…, \$\endgroup\$ Commented Feb 10, 2016 at 22:05
  • \$\begingroup\$ @Cyoce i make changes but when i defined r=[0] in default parameter r become nonlocal \$\endgroup\$ Commented Feb 11, 2016 at 7:05
  • \$\begingroup\$ you're right, I forgot how Python handled default params. The other tip should work though \$\endgroup\$ Commented Feb 11, 2016 at 7:26
3
\$\begingroup\$

C (gcc), 37 bytes

o(int*_){for(;*++_;)*_*=_[~0]/ *_+1;}

Try it online!

Improve this answer
\$\endgroup\$
1
3
\$\begingroup\$

TI-Basic, 43 40 37 bytes

Prompt A For(I,1,dim(ʟA ʟA(I)(1+int(Ans/ʟA(I→ʟA(I End ʟA

-6 bytes thanks to MarcMush.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ 37 bytes with a fresh calculator or Ans = 0 \$\endgroup\$ Commented May 16, 2022 at 16:16
2
\$\begingroup\$

Brachylog, 54 bytes

:_{h_.|[L:T],LhH,(T_,IH;0:$Ie*H=:T>I),Lb:I:1&:[I]rc.}.

Explanation

:_{...}. § Call sub-predicate 1 with [Input, []] as input. Unify its output § with the output of the main predicate § Sub-predicate 1 h_. § If the first element of the input is an empty list, unify the § output with the empty list | § Else [L:T],LhH, § Input = [L,T], first element of L is H (T_,IH § If T is the empty list, I = H ; § Else 0:$Ie*H=:T>I), § Enumerate integers between 0 and +inf, stop and unify the § enumerated integer with I only if I*H > T Lb:I:1& § Call sub-predicate 1 with input [L minus its first element, I] :[I]rc. § Unify the output of the sub-predicate with § [I|Output of the recursive call]
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Pyth, 11

t.u*Yh/NYQ0

Test Suite

Does a cumulative reduce, a reduce that returns all intermediate values, starting with 0. Since the input is guaranteed to contain only positive integers, this is ok. In each step, we take the old value, divide it by the new value and add 1, then we multiply by the new value.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

C, 79 bytes

p;main(x,v)char**v;{for(;*++v;printf("%d ",p=((x+p-1)/x+!(p%x))*x))x=atoi(*v);}

Ungolfed

p; /* previous value */ main(x,v) char**v; { /* While arguments, print out x such that x[i] > x[i-1] */ for(;*++v; printf("%d ", p = ((x+p-1)/x + !(p%x)) * x)) x = atoi(*v); }
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Wouldn't p=p/x*x+x work? \$\endgroup\$ Commented Feb 9, 2016 at 18:57
  • \$\begingroup\$ @Neil Yeah, that would work. Definitely overthought this one :) \$\endgroup\$ Commented Feb 9, 2016 at 19:04
2
\$\begingroup\$

PowerShell, 26 bytes

$args[0]|%{($l+=$_-$l%$_)}

Takes input as an explicit array, e.g., > .\sort-by-multiplying.ps1 @(6,5,4,3,2,1) via $args[0].

We then for-loop over that with |%{...} and each iteration perform magic. Nah, just kidding, we use the same modulo trick as other answers (props to @aross because I spotted it there first).

The encapsulating parens (...) ensure that the result of the math operation is placed on the pipeline, and thus output. If we left those off, nothing would be output since the $l variable is garbage-collected after execution finishes.

Example

PS C:\Tools\Scripts\golfing> .\sort-by-multiplying.ps1 @(8,9,1,5,4) 8 9 10 15 16
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Julia 1.0, 27 bytes

!L=(x=0;L.|>i->x=(x÷i+1)i)

Try it online!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Factor, 35 bytes

[ 0 [ tuck /i 1 + * ] accumulate* ]

Attempt This Online!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

PARI/GP, 25 bytes

a->i=0;[i=c*(i\c+1)|c<-a]

Attempt This Online!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Desmos, 78 bytes

n->min(n,i.length)+1,o->join(o,i[n]floor(o[n-1]/i[n]+1)) i=\ans_0 n=2 o=[i[1]]

Try It On Desmos!

Try It On Desmos! - Prettified

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Rust, 59 bytes

|mut l:Vec<u8>|{for i in 1..l.len(){l[i]*=l[i-1]/l[i]+1};l}

Try it online!

I am still learning rust, but I am sure there is a better solution using iter(). Also I am using u8 because the examples don't have output value greater than 512.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Uiua, 9 bytes

\(×+1⌊÷,)

Try it!

\(×+1⌊÷,) \( ) # scan by , # over ÷ # divide ⌊ # floor +1 # increment × # multiply
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Uiua, 8 bytes

\(-⊃◿+∶)

Try it online!

Given the previous value x and the next value y, the transformed y is the same as (x+y) - (x+y)%y == (x+y) - x%y.

\(-⊃◿+∶) input: a vector of positive integers \( ) scan by: (input: [x y]) : swap [y x] ⊃◿+ fork (mod, add) [x%y x+y] - subtract [x+y-x%y]
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Japt, 11 bytes

Uå@Y*-~(X/Y

Test it online!

How it works

 // Implicit: U = input array of integers Uå@ // Cumulative reduce: map each previous value X and current value Y to: -~(X/Y // floor(X/Y+1). // Implicit: output last expression
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 11 bytes

Code:

R`[=sŽDŠ/ò*

Try it online!

Explanation:

R # Reverse input ` # Flatten the list [ # While loop = # Print the last item s # Swap the last two items Ž # If the stack is empty, break D # Duplicate top of the stack Š # Pop a,b,c and push c,a,b / # Divide a / b ò # Inclusive round up * # Multiply the last two items

Uses CP-1252 encoding.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Minkolang 0.15, 17 bytes

nd1+?.z0c:1+*d$zN

Try it here!

Explanation

nd Take number from input and duplicate it 1+ Add 1 ?. Stop if top of stack is 0 (i.e., when n => -1 because input is empty). z Push value from register 0c Copy first item on stack : Pop b,a and push a//b 1+ Add 1 * Multiply d$z Duplicate and store in register N Output as number

Essentially, the register keeps the latest member of the ascending list and this is divided by the input and incremented to get the multiplier for the next member. The toroidal feature of Minkolang's code field means that it loops horizontally without the need for () or [] loops.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Brachylog, 21 bytes

l~lCℕ₁ᵐ≤ᵛ~+?&;Cz≜×ᵐ<₁

Try it online!

Uses the sum of input values as the upper bound for coefficients C. Pretty slow, times out on TIO for input list lengths beyond 5 or 6 (also depending on the sum of the values). But not as slow as my original version, which requires tiny lists of upto 3 elements, with tiny values, to not time out:

21 bytes

l~l.&+^₂⟦₁⊇.;?z/ᵐℕ₁ᵐ∧

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Python 2, 53 bytes

lambda a:reduce(lambda b,v:b+[b[-1]/v*v+v],a,[0])[1:]

Try it online!

k*x>y implies k>y/x; so the smallest k can be is k=floor(y/x)+1. Since in Python 2.7, integer division is already taken as floor, we want k=y/x+1, and k*x = (y/x+1)*x = y/x*x+x.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

K (oK), 11 bytes

{y*1+_x%y}\

Try it online!

Improve this answer
\$\endgroup\$
1
2

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.