fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. struct person{
  4. 	string name;
  5. 	int age;
  6. };
  7. int main() {
  8. 	// vector<int> arr={3,2,3,3,2,4};
  9. 	// map<int,int> ok;
  10. 	// for(int i=0;i<arr.size();i++){
  11. 	// 	ok[arr[i]]++;
  12. 	// }
  13. 	// int maxl,minl,max=0,min=;
  14. 	// for(auto it=ok.begin();it!=ok.end();it++){
  15. 	// 	cout<<it->first<<"  "<<it->second<<endl;
  16. 	// 	if(it->second>max){
  17. 	// 		max=it->second;
  18. 	// 		maxl=it->first;
  19. 	// 	} 
  20. 	// 	if(it->second < min){
  21. 	// 		min=it->second;
  22. 	// 		minl=it->first;
  23. 	// 	}
  24. 	// }
  25. 	// cout<<"maxelement  "<<maxl<<"  freq  "<<max;
  26. 	// cout<<"minelement   "<<minl<<"    freq  "<<min;
  27.  
  28.  
  29. 	// vector<person> people;
  30. 	// people.push_back({"asha",22});
  31. 	// people.push_back({"prem",18});
  32. 	// people.push_back({"anu",48});
  33. 	// for(auto& it:people){
  34. 	// 	cout<<(it).name<<endl; //here it is a reference variable
  35. 	// }
  36.  
  37. 	// map<string,person> ok;
  38. 	// ok["asha"]={"asha",22};
  39. 	// ok["prem"]={"prem",18};
  40. 	// ok["anu"]={"anu",23};
  41.  
  42. 	// for(auto& it:ok){
  43. 	// 	cout<<it.second.age<<endl;
  44. 	// }
  45.  
  46. 	// for(auto it=ok.begin();it!=ok.end();it++){
  47. 	// 	cout<<it->second.age<<endl;
  48. 	// }
  49. 	// cout<<ok["asha"].name<<endl;
  50.  
  51. 	// --check if there are any two equal numbers in an array at a distance less than or equal to k--
  52. 	// brute force o(n2)
  53. 	// int arr[]={1,2,1,3,4,2,3,3};
  54. 	// int k=2,count=0;
  55. 	// for(int i=0;i<7;i++){
  56. 	// 	for(int j=i+1;j<=i+k && j<8;j++){
  57. 	// 		if(arr[i]==arr[j]){
  58. 	// 			count++;
  59. 	// 		}
  60. 	// 	}
  61. 	// }
  62. 	// cout<<count;
  63.  
  64. 	//hashmap
  65. 	// int arr[]={1,2,1,3,4,2,3,3};
  66. 	// int k=2,count=0;
  67. 	// unordered_map<int,int>ok;
  68. 	// for(int i=0;i<8;i++){
  69. 	// 	if(ok.find(arr[i])!=ok.end() && i-ok[arr[i]]<=k){
  70. 	// 		count++;
  71. 	// 	}
  72. 	// 	ok[arr[i]]=i;
  73.  
  74. 	// }
  75. 	// cout<<count<<endl;
  76. 	// for(auto it=ok.begin();it!=ok.end();it++){
  77. 	// 	cout<<it->first<<"     "<<it->second<<endl;
  78. 	// }
  79.  
  80.  
  81. 	//count all the i j pairs i<j such that arr[i]+arr[j]==k
  82. 	// brute force
  83. 	// int arr[]={1,2,1,3,4,2,3,3};
  84. 	// int k=3,count=0;
  85. 	// for(int i=0;i<8;i++){
  86. 	// 	for(int j=i+1;j<8;j++){
  87. 	// 		if(arr[i]+arr[j]==k){
  88. 	// 			count++;
  89. 	// 			cout<<i<<"     "<<j<<endl;
  90. 	// 		}
  91. 	// 	}
  92. 	// }
  93. 	// cout<<count<<endl;
  94.  
  95. 	//hashmap
  96. 	// unordered_map<int,int> ok;
  97. 	// int arr[]={1,2,1,3,4,2,3,3};
  98. 	// int k=2,count=0;
  99. 	// for(int i=0;i<8;i++){
  100. 	// 	if(ok.find(k-arr[i])!=ok.end()){
  101. 	// 		auto it=ok.find(k-arr[i]);
  102. 	// 		count+=it->second;
  103. 	// 	}
  104. 	// 	ok[arr[i]]++;
  105. 	// }
  106. 	// cout<<count<<endl;
  107.  
  108.  
  109. 	// // count all the i j pairs i<j such that arr[i]-arr[j]==k
  110. 	// brute force
  111. 	// int arr[]={1,2,1,3,4,2,3,3};
  112. 	// int k=1,count=0;
  113. 	// for(int i=0;i<8;i++){
  114. 	// 	for(int j=i+1;j<8;j++){
  115. 	// 		if(arr[i]-arr[j]==k){
  116. 	// 			count++;
  117. 	// 			cout<<i<<"     "<<j<<endl;
  118. 	// 		}
  119. 	// 	}
  120. 	// }
  121. 	// cout<<count<<endl;
  122.  
  123.  
  124. 	//hashmap
  125. 	// unordered_map<int,int> ok;
  126. 	// int arr[]={1,2,1,3,4,2,3,3};
  127. 	// int k=1,count=0;
  128. 	// for(int i=0;i<8;i++){
  129. 	// 	if(ok.find(k+arr[i])!=ok.end()){
  130. 	// 		auto it=ok.find(k+arr[i]);
  131. 	// 		count+=it->second;
  132. 	// 	}
  133. 	// 	ok[arr[i]]++;
  134. 	// }
  135. 	// cout<<count<<endl;
  136.  
  137. 	// count all the i j pairs i<j such that abs(arr[i]-arr[j])==k
  138. 	// brute force
  139. 	// int arr[]={1,2,1,3,4,2,3,3};
  140. 	// int k=1,count=0;
  141. 	// for(int i=0;i<8;i++){
  142. 	// 	for(int j=i+1;j<8;j++){
  143. 	// 		if(abs(arr[i]-arr[j])==k){
  144. 	// 			count++;
  145. 	// 			cout<<i<<"     "<<j<<endl;
  146. 	// 		}
  147. 	// 	}
  148. 	// }
  149. 	// cout<<count<<endl;
  150.  
  151. 	//hashmap
  152. 	// unordered_map<int,int> ok;
  153. 	// int arr[]={1,2,1,3,4,2,3,3};
  154. 	// int k=1,count=0;
  155. 	// for(int i=0;i<8;i++){
  156. 	// 	int complement1=arr[i]-k;
  157. 	// 	int complement2=k+arr[i];
  158. 	// 	if(ok.find(complement1)!=ok.end()){
  159. 	// 		count+=ok[complement1];
  160. 	// 	}
  161. 	// 	if(ok.find(complement2)!=ok.end()){
  162. 	// 		count+=ok[complement2];
  163. 	// 	}
  164. 	// 	ok[arr[i]]++;
  165.  
  166. 	// }
  167. 	// cout<<count<<endl;
  168.  
  169.  
  170. 	//-------prefix sum--------
  171. 	// int arr[]={3,4,1,2,1,4};
  172. 	// int l=2 ,r=5;
  173. 	// for(int i=1;i<6;i++){
  174. 	// 	arr[i]+=arr[i-1];
  175. 	// }
  176. 	// cout<<arr[r]-arr[l-1];
  177.  
  178.  
  179. 	//count the total number of subarrays with sum==k;
  180. 	//brute force O(n2)
  181. 	// int arr[]={1,0,1,2,0,10,5};
  182. 	// int k=4;
  183. 	// int count=0;
  184. 	// for(int i=0;i<7;i++){
  185. 	// 	int sum=arr[i];
  186. 	// 	for(int j=i+1;j<7;j++){
  187. 	// 		sum+=arr[j];
  188. 	// 		if(sum==k){
  189. 	// 			count++;
  190. 	// 			cout<<i<<"    "<<j<<endl;
  191.  
  192. 	// 		}
  193. 	// 	}
  194. 	// }
  195. 	// cout<<count<<endl;
  196.  
  197.  
  198. 	//brute force part 2
  199. 	int arr[]={1,0,1,2,0,10,5};
  200. 	int arr1[]={0,0,0,3,0,0,0};
  201. 	int prefix[8]={0}; // prefix sum size will be one more than arr
  202. 	int totalsubarrays=0;
  203.  
  204. 	int k=3;
  205. 	for(int i=1;i<8;i++){
  206. 		prefix[i]=prefix[i-1]+arr1[i-1];
  207. 	}
  208. 	int count=0;
  209. 	for(int i=1;i<8;i++){
  210. 		for(int j=0;j<=i;j++){
  211. 			 if(prefix[i]-k==prefix[j]){
  212. 				count++;
  213. 				cout<<j<<"    "<<i-1<<endl;
  214. 			 }// hume ye to pata hai ki sum ==k to hoga subarray ka
  215. 			totalsubarrays++;
  216. 		}
  217. 	}
  218. 	cout<<totalsubarrays<<endl;
  219. 	cout<<count<<endl;
  220.  
  221.  
  222.  
  223.  
  224.  
  225.  
  226.  
  227.  
  228.  
  229.  
  230.  
  231.  
  232.  
  233.  
  234. 	return 0;
  235. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0    3
1    3
2    3
3    3
0    4
1    4
2    4
3    4
0    5
1    5
2    5
3    5
0    6
1    6
2    6
3    6
35
16
https://ideone.com/OQXiS6
Hashing
language:
C++14 (gcc 8.3)
created:
6 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!