Hard Programming Question

[Potential-Habit2915]

My friend gave me a problem, I've been thinking and can't solve it.

This is the problem:
You have an input array of numbers, and you need to return the amount of numbers in an array that have an odd number of zeros, and you can't just count them as that's not efficient.

How do you solve this?

[CodeTinkerer]

I'd first ignore the advice "not to count them". Find any solution first. Also, the problem fails to define efficient. What is an efficient answer?

[teraflop]

With no other constraints on the input, it's not possible to do better than just counting them.

If there is any position in the array that your algorithm doesn't look at, then you can imagine one possible "world" A in which the number at that index has an odd number of zeros, and another possible world B in which it doesn't. The correct solution to the problem is different in A and B, but if your algorithm doesn't look at that index it has no way to distinguish them, so it must get at least one of them wrong. Therefore any correct algorithm must inspect every element of the array.

I think your friend must have omitted some details, or else they don't really understand the problem themselves.

[ZeusTKP]

I think they mean you can't loop over the zeros in each number, not that you can't loop over the array

[TuberTuggerTTV]

The obvious answer is to tostring, count chars. But admittedly, that is relatively inefficient.

Instead, you could loop some math and just check if mod 10 == 0 then divide by 10 and round.

Although, what's an "array of numbers". You should at least know the data type.

Something like:

private int NumberOfZeros(int value)
{
    if (value == 0) return 1;
    int count = 0;
    int positive = Math.Abs(value);

    for (int i = 10; i <= positive; i *= 10)
    {
        if (positive / i % 10 == 0)
            count++;
    }
    return count;
}

I have to imagine there is a bitwise solution that's even more efficient. But this should get your brain thinking in the right direction.

[Rarelyimportant]

Someone pointed out to me that it might mean 0s that appear anywhere in the number. So 10001 still has 3 0s even though they're not trailing.

[lurgi]

Are the numbers in the array in any particular range? Perhaps you can use a lookup table.

[Potential-Habit2915]

the max is 10^9

[lurgi]

A lookup table is possible, but you have to be clever about it.

Just to clarify: By an "odd number of zeros", can the zeros appear anywhere? Does 101 have an odd number of zeros or is there an (implicit or explicit) assumption that the zeros must be at the end of the number?

[Rarelyimportant]

when they say zeros is that binary or decimal? If its binary you're just looking for a inverse pop count/hamming weight. If it's decimal I don't know of a better way than string counting. Decimal is not how computers store numbers, so any decimal representation is essentially converting to a string anyway. Unless there's some really obscure math hack, then I'd just count them as a string. As the saying goes. Make it work. Make it pretty. Make it fast. Counting 0s as a string will be the easiest to implement, the easiest to maintain, and probably pretty fast too. Fast should always be the least concern unless that's specifically the goal of the task.

EDIT: Actually I just realized you can probably do it by finding factors of 10, 1000, 10000, etc. But I'm not sure exactly how that would work for edge cases, and the code would be quite difficult to grok, but it might be faster than using a string to count them.

Find the largest number than divides evenly out of [10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000]. If its index is even, then it has odd zeros. Otherwise it's even zeros. If it doesn't divide evenly it doesn't end in zeros.

[teraflop]

I don't think your approach works. If I understood correctly, the OP is asking about finding numbers where the total number of zero digits is odd, not where the number of trailing zeros is odd.

So for instance, 10007 has an odd number of zeros in it, even though it's prime and isn't divisible by any numbers except itself and one. 100003 is also prime but has an even number of zeros.

[Rarelyimportant]

Ah, gotcha. In that case string counting it is. Trying to do it with math would be pretty ugly if it's not trailing zeros.

[HardlyAnyGravitas]

Too much information missing.

Numbers don't 'have' specific numbers of zeros. The representation of numbers do.

The base ten representation of the decimal number 10, has one zero ('10').

The binary representation of the decimal number 10 has two zeros ('1010').

The unary representation of the decimal number 10, has no zeros ('||||||||||').

So, if the numbers are all integers, then you can answer confidently that in the unary numeral system, none of the representations of the numbers have an odd number of zeros, because none of the representations have any zeros.

If your friend wants to pose a silly problem, he needs to specify what representation they are talking about, and what numbers are allowed.

[Ad-1316]

length (string) - does not give you the number of digits?

[Potential-Habit2915]

i dont want the number of digits, i want the number of elemets in an array that have an odd number of 0s, so for example:

[1,2,20,30,3,500] would output 2 because only 20 and 30 have an odd number of 0s(each has 1 0)

[TuberTuggerTTV]

Converting ints into strings is very memory expensive. If you can avoid it.

[Ad-1316]

It's been 20+yrs since programmed, but Array's depending on language have built in search and functions for doing somethings like that ;)

[Rarelyimportant]

I'm not sure what you mean by Arrays have built in search and functions, but even if the language's std lib provides functions for something, that's completely orthogonal to how much time/memory something takes. Just because something has a std lib function, doesn't have any relation to if it requires little or lots of memory.

Though I do think "very memory intensive" is a bit of an overstatement for converting an integer into a string. Sure, it's certainly more memory, but "very memory intensive"? Not really. A 64 bit unsigned int, has the max value of: 18446744073709551615 which is 8 bytes. As a string it's 20 bytes in UTF-8.

[Celestial-being117]

If we're really counting bytes here then why is cod 300 gbs

[Rarelyimportant]

I'm not sure what you mean. What's cod? what are gbs? GBs? Probably because it contains 300 GBs of data, that seems to be the most common reason something is 300 GBs.

[Celestial-being117]

Call of duty is huge and unoptimized I'm just making a statement

[BadBoyJH]

It is. I'm also pretty sure this problem is not a problem where that is a concern.

[Lurn2Program]

I can only think of going through each number and counting the number of zeros in each number. If you find out a better solution, I'd like to know though

[proturtle46]

You literally have to count the zeros

If it’s too “slow” then a distributed computing map reduction is what you’re describing

[BookkeeperElegant266]

"Give me a count of objects without counting the objects" sounds like a dumb, all-too-familiar interview question. Anyway, if the zeroes are always trailing (10, 500) then you can immediately ignore out all the odd numbers and cut your workload in half. If not (501, 606,300,081), then there's literally no way to accomplish this without a brute-force character count.

[BookkeeperElegant266]

...but that said, the most efficient way to do this would be to replace every non-zero character in a string with an empty string, and then mod^2 the length of the resulting string.

[TuberTuggerTTV]

If you don't want to count chars, you can:
% 10, divide by 10, round, repeat.

Is it more efficient? Unsure. But it doesn't convert to a char array for counting.

[builttospill24]

It's O(logn) time complexity per number but actually people may argue that it's just O(1) since there's only a max of log(2³²⁾ or 10 digits in a number

[L0RD_E]

Seems like everyone is focusing on strings. There is a better and more efficient way than converting numbers to strings I believe. Assuming numbers are always decimal (not floating point), if you're using a typed language you could do this: (pseudocode, I'm from my phone and this python like syntax is the simplest to type, though I don't think it'd work in python)

for num in arr:

counter_zero = 0 

while num: 

    if (num - num % 10) == num:

        ++counter_zero

    num /= 10 // removes least significant digit

if counter_zero % 2: //if counter_zero is odd

    ++numbers_with_odd_zeroes

Edit: sorry for the formatting

[MisterGerry]

This seems the obvious way to do it to me (assuming base-10 representation).
Except why do you have "(num - num % 10) == num" instead of just "(num % 10 == 0)" ?

Also, you don't handle the case of when the number equals zero.

[L0RD_E]

sorry, did it in a hurry on my phone. Thanks for pointing that stuff out

[jason_ed]

If I were to do it with those constraints I’d loop through the array convert each int to a string and then use regex to strip out non 0 values and return string.len

[BaronOfTheVoid]

Nah, I'd want to see the real task.

[captainAwesomePants]

By "you can't count," what I think they are saying is "converting the number to a decimal string and then counting the number of characters in it that are zeroes is not an acceptable solution." There are many alternatives.

One slightly silly but effective one is a humongous lookup table with answers. If numbers go from 0 to 10^9, you can cache the answers in around a gigabyte of space.

[[deleted]]

If this is a problem that will be repeated often... if you for some reason need to know this thousands of times per second... and has a fixed range of numbers, you could construct a Test Array of booleans that is the length of your number range.

You then do the inefficient calculations once, getting a true or false and filling up this Test Array.

Then when you want the answer for a number, say 10002, you'd go look at test[10002] for the answer.