CODEWITHSUNDEEP
c++bit-manipulation
Prasath Govind
Prasath Govind

Reputation: 750

How to check if numbers 0 to 9 have appeared atleast once in a stream of numbers in C++?

There is a stream of incoming numbers (in Base 10, could be any number having 'n' digits, say the stream could be 123, 8, 670, 4835134, 50243)

I have to check if all the digits 0 to 9 have appeared after reading the entire stream.

Ex. if stream is 123, 8, 670, 48351934, 50243, then the answer is "TRUE" (from 0 till 9, a number has appeared at least once)

if the stream is 123, 8, 670, 4835134, 50243, then the answer is "FALSE" because 9 did not appear in any of the numbers in the stream

Fix - 1 I thought I can take Can take OR from 0 till 9 and have it (allORresult) Calucatate OR of all the numbers in the stream (streamORresult) If the set bits of allORresult and streamORresult are similar, then we can conclude all the numbers,0 to 9 have appeared atleast once in the numbers of the stream.

Fix - 2 Take the naive approach! Decompose the number starting from ones digit (%10 then /10) and set a flag for each digit. If all the digits are encountered, then return TRUE

Upvotes: 1

Views: 1060

Answers (3)

M.M
M.M

Reputation: 2304

Just throwing a function that may come in handy:

#include <iostream>
#include <vector>

using namespace std;

bool findAllDigits(istream & i){
    vector<int> digits(0);
    int tmp; char c; bool found;

    while(i >> c){//read one char
        if(isdigit(c)){//check if it is a number
            tmp = c - '0';//convert char to int
            found = false;
            for(size_t i = 0; i < digits.size(); ++i){
                if(tmp == digits[i]){
                    found = true; break;
                }
            }
            if(!found){//if this number wasn't in the vector yet
                digits.push_back(tmp);
            }
        }
    }
    return digits.size() == 10;//return true if all the digits are in the stream
}

IDEONE

More compact function that uses stl:

#include <algorithm>
bool findAllDigits(istream & i){
    vector<char> digits(0); char c;

    while(i >> c)//read one char
        if(isdigit(c) && find(digits.begin(), digits.end(), c)==digits.end())//check if it is a number and not in the vector
            digits.push_back(c);

    return digits.size() == 10;//return true if all the digits are in the stream
}

IDEONE

Upvotes: 1

Hemant Pathak
Hemant Pathak

Reputation: 68

you can scan the entire stream and use flags for each number form 0-9 http://ideone.com/yJ13SM

#include <iostream>
#include<stdio.h>
using namespace std;

int main() {
char ch;
int flags[10];
do{
    ch=getchar();
    cout<<ch;
    if(ch>='0' && ch<='9')
        flags[ch-'0'] = 1;
}while(ch!='\n'); // some condition to stop scanning further
int flag = 0;
for(int i=0;i<=9;i++)
    if(!flags[i])
        flag++;
if(flag)
    cout<<"some digit was missing";
else
    cout<<"good coverage";
return 0;
}

Upvotes: 1

Christophe
Christophe

Reputation: 73456

The bit manipulation will not help you for this problem: 

decimal      binary          
  123       0111 1011               
    2       0000 0010
   OR       0111 1011

You have either to convert the number to strings (or keep them as such) and process the characters that represent the digits, or you have to iterate using %10 to get the last digit and use /10 to process the next digit.

I leave you finish your exercise with this hint on your own.

Upvotes: 1

Related Questions