दिया गया कार्य निम्नलिखित प्रतिबंधों के साथ एक बाइनरी मैट्रिक्स में अधिकतम 1 की संख्या ढूंढना है।
दो पूर्णांक N और X दिए गए हैं जहां X <= N। बाइनरी मैट्रिक्स का आकार N*N होना चाहिए और आकार X*X के प्रत्येक सब-मैट्रिक्स में कम से कम एक शून्य होना चाहिए।
उदाहरण से समझते हैं
इनपुट - N=4, X=2
आउटपुट - 12
व्याख्या - परिणामी मैट्रिक्स होगा -
1 1 1 1 1 0 0 1 1 0 0 1 1 1 1 1
इनपुट - N=7, X=3
आउटपुट - 45
प्रयुक्त दृष्टिकोण
अधिकतम 1 की संख्या प्राप्त करने के लिए, पहले हमें दिए गए मैट्रिक्स में आवश्यक न्यूनतम शून्य की संख्या ढूंढनी होगी।
सभी मैट्रिक्स में एक सामान्य पैटर्न देखकर, यह देखा जा सकता है कि आवश्यक शून्य की संख्या = (N / X)²
इसलिए अधिकतम 1 की संख्या = मैट्रिक्स में कुल तत्व - शून्य की संख्या
MaxOne() फंक्शन में Z टाइप का एक वेरिएबल बनाएं और इसमें आवश्यक न्यूनतम शून्य की संख्या स्टोर करें जो (N / X)² के बराबर है।
फिर total = N*N टाइप का एक और वेरिएबल आरंभ करें मैट्रिक्स का कुल आकार स्टोर करने के लिए।
फिर अंत में int ans = total - Z आरंभ करें अंतिम उत्तर स्टोर करने के लिए और ans वापस करें।
C++ प्रोग्राम उदाहरण
#include <bits/stdc++.h>
using namespace std;
int MaxOne(int N, int X) {
// आवश्यक न्यूनतम शून्य की संख्या
int Z = (N / X);
Z = Z * Z;
/* मैट्रिक्स में कुल तत्व = मैट्रिक्स के आकार का वर्ग */
int total = N * N;
// अंतिम उत्तर
int ans = total - Z;
return ans;
}
int main() {
int N = 4;
int X = 2;
cout << MaxOne(N, X);
return 0;
}आउटपुट
12
