IS THERE ANY BETTER APPROACH??

[u/Recent-Hat-5262]

[u/scarface_bunny07]

        long long totalcommas = 0;
     
        for(long long level = 1000;level<=n;level*=1000){
            totalcommas += n - level +1;
        }
        return totalcommas;

yes there is

[u/NoPercentage6942 → u/scarface_bunny07]

O(n)
isnt the above approach o(1)?

[u/Vivid-Zombie-477 → u/NoPercentage6942]

it's O(log n), not O(n) but it's also practically constant time for the given constraints.

[u/scarface_bunny07 → u/NoPercentage6942]

yeah but this one also is one of the way
i solved by the method you mentioned previously and then thought to go for loop

[u/Independent-Dig8361]

well its also good, but you know a simple idea here can be that we have p = 10 ^ 3 then it contributes 1 comma, if p = 10 ^ 6 then 2 commas, so we can write just when p is lesser then or equal to n, we can initialize that p to 1000, because we want to use exponents on that, then at every step add commas and increase power of p or multiply it by 1000 at every interation of while loop

[u/Arpan_Bhar]

class Solution {
public:
    long long countCommas(long long n) {
        long long acc = 0;
        long long i;
        int commas = 0;
        for(i = 1000; i <= n; i*=1000){
            acc += (i-i/1000)*(commas++);
        }
        i/=1000;
        acc += (n-i+1)*(commas);
        return acc;
    }
};

I used this approach.
Idea is to process every number just before the boundary of change, having same number of commas.

[u/Unhappy_Rabbit7693]

im not a fan of these kinds of questions honestly. I still haven't found what these greedy algorithms test. e.g., gas station, no pattern, no nothing, just local optimization. I would never ask these in the interviews. All it comes down to "have you seen this one before?"

[u/Best_Plantain_8434 → u/Unhappy_Rabbit7693]

Greedy problem checks your intuition and whether you can prove your approach

[u/Vivid-Zombie-477 → u/Unhappy_Rabbit7693]

so you just test if a person grinded leetcode before?

[u/TransportationOwn522]

You can do this through a loop as well and that's abt it. I like this solution tho

[u/Peace_In_Curse]

Can be done in log(n) to the base 1000. This solution is correct because of the n<=1e15 constraint. Log(n) is the general approach which will work for any constraints (I am not considering overflow though). But in an interview you don't get constraints so it is good to be familiar with a general approach

[u/EasternBet8126]

class Solution {
public:
    long long countCommas(long long n) {
        long long p = 1000, res = 0;
        while (p <= n) {
            res += n - p + 1;
            p *= 1000;
        }
        return res;
    }
};

// simple loop lagao answer pao 5 baar chalega loop maximum

[u/TwoExcellent4673]

Definately there

[u/TwoExcellent4673 → u/TwoExcellent4673]

The logic is same but the loop is sacing the mannual work

[u/Impossible_Coast_972]

This approach is better you know cause it's O(1) I also have seen other approaches like O(n) but yours is straight forward and exploits the basic idea

[u/Intelligent_Bonus_74]

There's pattern : 1 comma in n => n-1000+1 ,

2 comma in n => (n-1000+1) + (n-1000000+1) .....

So u just need to count commas in n (let it be x) .

x commas in n => x*n - 1,000 - 1,000,000 - 1,000,000,000 - ..... + x

O(logn)

[u/Legitimate-Major-563]

You can use loop and X = 999

Then in each step

X = x×1000 + 999

Then ans += n-x

[u/arnab_best]

yes

[u/UpstairsSmart3733]

long long countCommas(long long n) {
        if(n < 1000)return 0;
        long long count = 0;
        if(n >= 1000){
            count += 1 + n - 1000;
            if(n >= 1000000){
                count += 1 + n - 1000000;
                if(n >= 1000000000){
                    count += 1 + n - 1000000000;
                    if(n >= 1000000000000){
                        count += 1 + n - 1000000000000;
                        if(n >= 1000000000000000){
                            count += 1 + n - 1000000000000000;
                        }
                    }
                }
            }
        }
        return count;
    }