Problem: Find a multiple of a given decimal number \$N\$ that looks like a binary number.
The input will consist of at most \2ドル\times10^5\$\$ 2 \times 10^5 \$ lines, each line consist of an integer \$N\$ (\0ドル < N < 10^{12}\$\0ドル \lt N \lt 10^{12} \$). Find its described multiple\$M\$ (\$M != 0\$\$M (\ne 0\$), this number \$M\$ must be less than \10ドル^{12}\$. If there is no such number, print '\$-1\$'on' on the output.
My solution to this problem is quite simple. Just generated all binary-like numbers less than \10ドル^{12}\$ excluding \0ドル\$ (there are \4095ドル\$ such numbers).
For each number from input, just do a linear search on the binary numbers list. Is it possible to do it faster?
#include <cstdio>
#include <vector>
std::vector<long long> bits;
void generateBits(){
for (int i = 1; i < 4096; ++i) {
long long e = 1; //e is the exponencial of 10
long long n = i; //n will be used to extract the bits from the number i
long long d = 0;//binary-like decimal number...
while (n) {
d += ((n&1)*e);
n >>= 1, e *= 10;
}
bits.push_back(d);
}
}
long long getBitMultiple(long long n){
for (auto &bit : bits) {
if(bit%n == 0){
return bit;
}
}
return -1;
}
int main(void){
generateBits();
long long n;
while (scanf("%lld",&n) != EOF) {
printf("%lld\n",getBitMultiple(n));
}
return 0;
}
Problem: Find a multiple of a given decimal number \$N\$ that looks like a binary number.
The input will consist of at most \2ドル\times10^5\$ lines, each line consist of an integer \$N\$ (\0ドル < N < 10^{12}\$). Find its described multiple\$M\$ (\$M != 0\$), this number \$M\$ must be less than \10ドル^{12}\$. If there is no such number, print '\$-1\$'on the output.
My solution to this problem is quite simple. Just generated all binary-like numbers less than \10ドル^{12}\$ excluding \0ドル\$ (there are \4095ドル\$ such numbers).
For each number from input, just do a linear search on the binary numbers list. Is it possible to do it faster?
#include <cstdio>
#include <vector>
std::vector<long long> bits;
void generateBits(){
for (int i = 1; i < 4096; ++i) {
long long e = 1; //e is the exponencial of 10
long long n = i; //n will be used to extract the bits from the number i
long long d = 0;//binary-like decimal number...
while (n) {
d += ((n&1)*e);
n >>= 1, e *= 10;
}
bits.push_back(d);
}
}
long long getBitMultiple(long long n){
for (auto &bit : bits) {
if(bit%n == 0){
return bit;
}
}
return -1;
}
int main(void){
generateBits();
long long n;
while (scanf("%lld",&n) != EOF) {
printf("%lld\n",getBitMultiple(n));
}
return 0;
}
Problem: Find a multiple of a given decimal number \$N\$ that looks like a binary number.
The input will consist of at most \$ 2 \times 10^5 \$ lines, each line consist of an integer \$N\$ (\0ドル \lt N \lt 10^{12} \$). Find its described multiple \$M (\ne 0\$), this number \$M\$ must be less than \10ドル^{12}\$. If there is no such number, print '\$-1\$' on the output.
My solution to this problem is quite simple. Just generated all binary-like numbers less than \10ドル^{12}\$ excluding \0ドル\$ (there are \4095ドル\$ such numbers).
For each number from input, just do a linear search on the binary numbers list. Is it possible to do it faster?
#include <cstdio>
#include <vector>
std::vector<long long> bits;
void generateBits(){
for (int i = 1; i < 4096; ++i) {
long long e = 1; //e is the exponencial of 10
long long n = i; //n will be used to extract the bits from the number i
long long d = 0;//binary-like decimal number...
while (n) {
d += ((n&1)*e);
n >>= 1, e *= 10;
}
bits.push_back(d);
}
}
long long getBitMultiple(long long n){
for (auto &bit : bits) {
if(bit%n == 0){
return bit;
}
}
return -1;
}
int main(void){
generateBits();
long long n;
while (scanf("%lld",&n) != EOF) {
printf("%lld\n",getBitMultiple(n));
}
return 0;
}
Problem: Find a multiple of a given decimal number N\$N\$ that looks like a binary number.
The input will consist of at most 2*10^5\2ドル\times10^5\$ lines, each line consist of an integer N\$N\$ (0 < N < 10^12\0ドル < N < 10^{12}\$). Find its described multiple M\$M\$ (M != 0\$M != 0\$), this number M\$M\$ must be less than 10^12\10ドル^{12}\$. If there is no such number, print '-1'on\$-1\$'on the output.
My solution to this problem is quite simple. Just generated all binary-like numbers less than 10^12\10ドル^{12}\$ excluding 0 \0ドル\$(there are 4095\4095ドル\$ such numbers).
For each number from input, just do a linear search on the binary numbers list. It'sIs it possible to do it faster?
#include <cstdio>
#include <vector>
std::vector<long long> bits;
void generateBits(){
for (int i = 1; i < 4096; ++i) {
long long e = 1; //e is the exponencial of 10
long long n = i; //n will be used to extract the bits from the number i
long long d = 0;//binary-like decimal number...
while (n) {
d += ((n&1)*e);
n >>= 1, e *= 10;
}
bits.push_back(d);
}
}
long long getBitMultiple(long long n){
for (auto &bit : bits) {
if(bit%n == 0){
return bit;
}
}
return -1;
}
int main(void){
generateBits();
long long n;
while (scanf("%lld",&n) != EOF) {
printf("%lld\n",getBitMultiple(n));
}
return 0;
}
Problem: Find a multiple of a given decimal number N that looks like a binary number.
The input will consist of at most 2*10^5 lines, each line consist of an integer N (0 < N < 10^12). Find its described multiple M (M != 0), this number M must be less than 10^12. If there is no such number, print '-1'on the output.
My solution to this problem is quite simple. Just generated all binary-like numbers less than 10^12 excluding 0 (there are 4095 such numbers).
For each number from input just do a linear search on the binary numbers list. It's possible to do it faster?
#include <cstdio>
#include <vector>
std::vector<long long> bits;
void generateBits(){
for (int i = 1; i < 4096; ++i) {
long long e = 1; //e is the exponencial of 10
long long n = i; //n will be used to extract the bits from the number i
long long d = 0;//binary-like decimal number...
while (n) {
d += ((n&1)*e);
n >>= 1, e *= 10;
}
bits.push_back(d);
}
}
long long getBitMultiple(long long n){
for (auto &bit : bits) {
if(bit%n == 0){
return bit;
}
}
return -1;
}
int main(void){
generateBits();
long long n;
while (scanf("%lld",&n) != EOF) {
printf("%lld\n",getBitMultiple(n));
}
return 0;
}
Problem: Find a multiple of a given decimal number \$N\$ that looks like a binary number.
The input will consist of at most \2ドル\times10^5\$ lines, each line consist of an integer \$N\$ (\0ドル < N < 10^{12}\$). Find its described multiple \$M\$ (\$M != 0\$), this number \$M\$ must be less than \10ドル^{12}\$. If there is no such number, print '\$-1\$'on the output.
My solution to this problem is quite simple. Just generated all binary-like numbers less than \10ドル^{12}\$ excluding \0ドル\$(there are \4095ドル\$ such numbers).
For each number from input, just do a linear search on the binary numbers list. Is it possible to do it faster?
#include <cstdio>
#include <vector>
std::vector<long long> bits;
void generateBits(){
for (int i = 1; i < 4096; ++i) {
long long e = 1; //e is the exponencial of 10
long long n = i; //n will be used to extract the bits from the number i
long long d = 0;//binary-like decimal number...
while (n) {
d += ((n&1)*e);
n >>= 1, e *= 10;
}
bits.push_back(d);
}
}
long long getBitMultiple(long long n){
for (auto &bit : bits) {
if(bit%n == 0){
return bit;
}
}
return -1;
}
int main(void){
generateBits();
long long n;
while (scanf("%lld",&n) != EOF) {
printf("%lld\n",getBitMultiple(n));
}
return 0;
}