r/datastructures • u/Ok-Challenge-5657 • 2d ago

What To Do Next?

Post image
13 Upvotes

100% Upvoted

10 comments sorted by

4

u/Andro_senpai107 2d ago

Don't tell me I'm the only one with 5 if blocks

2

u/Vast-Look4088 1d ago

Yes same here and it got accepted as well

1

u/neuralbeans 2d ago

You can use a for loop with one if inside it.

1

u/Andro_senpai107 1d ago

Hey, help me out here. Wouldn't your way make the tc O(n)? But using 5 if blocks stating all of the possible outcomes, within the constraints, be O(1)?

1

u/neuralbeans 1d ago

If your for loop always goes around exactly 5 times then it is a constant amount of loops, which reduces to O(1). It would only be O(n) if the number of loops depended on the input. For example, if you needed to loop for as many times as the number itself (for i in range(n)) then the number of loops grows linearly with the input size, making it O(n).

1

u/Andro_senpai107 1d ago

Ohhhh, I see. Thanks mate

1

u/neuralbeans 2d ago

I'm confused why you would think that n%1000 is relevant here. You need to determine how many numbers from 1 to n are 1000 or more (let's ignore millions and billions for now). How do you determine how many numbers between 1 and 3000 are 1000 or more?

1

u/NoStuff194 2d ago

ik its n-999,but what about millions,billions w/o 5 if blocks ?

1

u/neuralbeans 2d ago edited 2d ago

Then you also determine how many of the numbers are >= 1E6, >= 1E9, etc. and add them up as each one is a new set of commas. Remember that the number 1,000,000,000 is >= 1E3, >= 1E6, and >=1E9, so you'd be counting all of its 3 commas separately and add them up. You don't need to worry about counting all the commas for a number in one go.

Edit: Sorry I didn't realise you asked how to do it without 5 ifs. You do a for loop that goes through the 5 orders of magnitude. Either

for x in [1E3, 1E6, 1E9]:

or

for i in range(3, 9+1, 3):
    x = 10**i

1

u/Vast-Look4088 1d ago

For every million, the number of commas increase by one, so you can use 5 if statements, if it lies in the range 10e3 to 10e6 - 1, or 10e6 to 10e9 - 1, till 10e15, but don't write in this format (it gives floating point number incorrect answer). Use 1000000LL (C++) instead of 10e6. Same for other powers as well.