Category: Math

Problem: Find  multiplication result of two large numbers in less than O(n^2) time complexity. #include <iostream> #include <string> /* 123456 34343 add=157799 sub=0@J113 */ using namespace std; void makeEqualString(string &a,string &b) { if(a.size()==b.size()) return; else { if(a.size()>b.size()) { for(int i=1;i<=a.size()-b.size();i++) b='0'+b; } else { for(int i=1;i<=b.size()-a.size();i++) a='0'+a; } } } string addString(string a,string b) {

Continue Reading “Karatsuba’s Fast Multiplication Algorithm” →

#include <iostream> #include <cstdio> #define ul unsigned long long//double//long long using namespace std; int main() { ul s,d,a,b; ul subtract; ul lw,hi,mid,res; while(scanf("%llu%llu",&s,&d)!=EOF) { if(d<=s) { printf("%llu\n",s); continue; } subtract=(s*(s-1))/2; lw=s; hi=s+d/s; res=-1; while(hi-lw>1) { mid=(lw+hi)/2; if(((mid*(mid+1))/2-subtract) <d) lw=mid+1; else if(((mid*(mid+1))/2-subtract)>d) hi=mid; else if(((mid*(mid+1))/2-subtract)==d) { res=mid; break; } } if(res!=-1) printf("%llu\n",res); else { //cout<<lw<<" "<<hi<<"\n";

Continue Reading “10170” →

#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <vector> #define ll long long using namespace std; ll arr[40001]; vector<int> vb; ll _pow(int pwr) { if(pwr==0) return 1; else return 10*_pow(pwr-1); } bool Isfunc(ll a,int b) { int tmp; tmp=a; int pwr=0; int num=0; while(tmp) { num=num + (tmp%10)*_pow(pwr); tmp/=10; if(tmp+num==b && tmp!=0 && num!=0)

Continue Reading “974” →

#include <iostream> #include <cstdio> #include <cstring> #include <string> using namespace std; int main() { int n,res; int positionInByte,byteNo; while(scanf("%d",&n)!=EOF) { res=0; for(int i=0;i<32;i++) { if((1<<i)&n) { byteNo=i/8; positionInByte=i%8; res |= (1<<((3-byteNo)*8+positionInByte)); } } printf("%d converts to %d\n",n,res); } return 0; }

#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <vector> #define ll long long #define LIMIT 9876543210 using namespace std; vector<int> vb; bool isRepeated(ll num) { if(num>=0 && num<=10) return 0; bool digits[10]; memset(digits,0,sizeof(digits)); while(num) { if(digits[num%10]) return 1; digits[num%10]=1; num/=10; } return 0; } int main() { int t; ll n; ll num; for(int

Continue Reading “471” →

#include <iostream> #include <cstdio> #include <cmath> #include <vector> #define ll long long #define MOD 1000000007 using namespace std; int _pow(int n,int p) { if(p==0) return 1; else return n*_pow(n,p-1); } int isAnyRoot(int a,int b) { if(a%b!=0) return -1; int cnt=0; while(a>=b) { cnt+=1; a=a/b; if(a>=b && a%b!=0) return -1; } return cnt; } int main()

Continue Reading “107” →