લંબચોરસ લિટકોડ સોલ્યુશન બનાવો


મુશ્કેલી સ્તર સરળ
મઠ

સમસ્યા લંબચોરસ લિટકોડ સોલ્યુશનનું નિર્માણ જણાવે છે કે તમે વેબ ડિઝાઇનર છો. અને તમને કેટલાક પૂર્વ નિર્ધારિત વિસ્તારવાળા વેબ પૃષ્ઠને ડિઝાઇન કરવાનું કાર્ય આપવામાં આવ્યું છે. ડિઝાઇન પર કેટલીક પ્રતિબંધો લાદવામાં આવી છે. વેબ પૃષ્ઠની લંબાઈ વેબ પૃષ્ઠની પહોળાઈ કરતા વધારે અથવા સમાન હોવી જરૂરી છે, ડિઝાઇન કરેલા વેબ પૃષ્ઠનું ક્ષેત્ર આપેલ ક્ષેત્રની સમાન હોવું જોઈએ. છેલ્લું પરંતુ ઓછામાં ઓછું નહીં, લંબાઈ અને પહોળાઈ વચ્ચેનો તફાવત શક્ય તેટલો નાનો હોવો જોઈએ. તેથી, ચાલો સમસ્યા હલ કરવા માટે ivingંડે ડાઇવ કરતાં પહેલાં કેટલાક ઉદાહરણો પર એક નજર કરીએ.

લંબચોરસ લિટકોડ સોલ્યુશન બનાવો

area = 4
[2,2]

સમજૂતી: 4 બરાબર વિસ્તારવાળા વેબ પૃષ્ઠની લંબાઈ અને પહોળાઈ ક્યાં તો 1 × 4 અથવા 2 either 2 હોઈ શકે છે. પરંતુ આપણે તેમની લંબાઈ અને પહોળાઈ શોધવાની જરૂર છે કે જેથી તેમની વચ્ચે ન્યૂનતમ તફાવત હોય. 2 × 2 પરિમાણો પસંદ કરવાનું વધુ સારું છે. 2 × 2 પરિમાણ પણ અનુસરે છે કે લંબાઈ પૃષ્ઠની પહોળાઈ કરતા વધારે અથવા બરાબર છે.

area = 23
[23, 1]

સ્પષ્ટતા: ક્ષેત્ર = 23 સાથે તમારી પાસે ફક્ત બે વેબ પૃષ્ઠો હોઈ શકે છે. તમારી પાસે પરિમાણો 23 × 1 અથવા 1 × 23 હોઈ શકે છે. પરિમાણો સાથેનું વેબ-પૃષ્ઠ 1 × 23 અમારી પ્રથમ શરતનું ઉલ્લંઘન કરે છે. અમારી પાસે ફક્ત 23 × 1 કદવાળા વેબ-પૃષ્ઠ હોઈ શકે છે.

લંબચોરસ લિટકોડ સોલ્યુશનના બાંધકામ માટે અભિગમ

સમસ્યાનો લંબચોરસ લિટકોડ સોલ્યુશન રચવા માટે અમને કેટલાક પૂર્વ-નિર્ધારિત વિસ્તારવાળા વેબ પૃષ્ઠનું યોગ્ય કદ શોધવા માટે કહે છે. વેબ-પૃષ્ઠ પરિમાણો લાદવામાં આવતી અવરોધને સંતોષવા જોઈએ. ત્રણ અવરોધો છે: લંબાઈ વેબ-પૃષ્ઠની પહોળાઈ કરતા વધારે અથવા તેની સમાન હોવી જોઈએ, ડિઝાઇન કરેલા વેબ પૃષ્ઠનું ક્ષેત્ર આપેલ ક્ષેત્ર જેટલું હોવું જોઈએ, લંબાઈ અને પહોળાઈ વચ્ચેનો તફાવત ઓછામાં ઓછો હોવો જોઈએ. આપેલ ક્ષેત્રના વર્ગમૂળથી ફક્ત પૂર્ણાંકો ઉપર લૂપ કરીને આપેલ અવરોધોને સંતોષતા પરિમાણોનો સમૂહ આપણે સરળતાથી શોધી શકીએ છીએ. અમે તપાસ કરતા રહીએ છીએ કે શું વર્તમાન પૂર્ણાંકો ક્ષેત્રને વિભાજિત કરે છે. જો તે થાય છે, તો અમે તપાસીએ છીએ કે તેના સમકક્ષ (વર્તમાન પૂર્ણાંક દ્વારા આપેલ ક્ષેત્રને વિભાજીત કરીને પ્રાપ્ત કરેલ ભાવિ) વચ્ચેનો તફાવત વર્તમાન સમૂહ કરતાં ઓછો તફાવત છે કે નહીં. જો બધી શરતો પૂરી થાય છે, તો અમે જવાબને અપડેટ કરીએ છીએ.

શરૂઆતમાં, અમે જવાબ એરીએક્સ 1 તરીકે સેટ કરીશું, કારણ કે તે હંમેશા આપેલ અવરોધોને સંતોષે છે. અને સોલ્યુશનમાં, અમે એક વધુ સારો સેટ કરવાનો પ્રયાસ કરીએ છીએ કે જેની વચ્ચે ઓછો તફાવત હોય. અંતે, અમે પરિમાણોને એ એરે.

લંબચોરસ સોલ્યુશનના બાંધકામ માટેનો કોડ

સી ++ કોડ

#include <bits/stdc++.h>
using namespace std;

vector<int> constructRectangle(int area) {
    vector<int> ans({area, 1});
    for(int i=1;i*i<=area;i++){
        if(area%i == 0 && (area/i - i)<(ans[0] - ans[1]))
            ans[0] = area/i, ans[1] = i;
    }
    return ans;
}

int main(){
    vector<int> ans = constructRectangle(4);
    cout<<ans[0]<<", "<<ans[1];
}
2, 2

જાવા કોડ

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
    public static int[] constructRectangle(int area) {
        int[] ans = {area, 1};
        for(int i=1;i*i<=area;i++){
            if(area%i == 0 && (area/i - i)<(ans[0] - ans[1])){
                ans[0] = area/i;
                ans[1] = i;
            }
        }
        return ans;
    }
    
  public static void main (String[] args) throws java.lang.Exception{
    int[] ans = constructRectangle(4);
    
    System.out.println(ans[0] + ", " + ans[1]);
  }
}
2, 2

જટિલતા વિશ્લેષણ

સમય જટિલતા

O (sqrt (N)), જ્યાં એન એ વિસ્તાર છે જે વપરાશકર્તાને પૂરો પાડવામાં આવે છે. કારણ કે આપણે આપેલા ક્ષેત્રના તમામ વિભાગોને તેના વર્ગમૂળ સુધી શોધવાનો પ્રયાસ કર્યો છે, આમ સમયની જટિલતા એ ઇનપુટનો વર્ગમૂળ છે.

અવકાશ જટિલતા

ઓ (1), કારણ કે આપણે ફક્ત સતત ચલોનો ઉપયોગ કર્યો છે. જગ્યાની જટિલતા પણ સતત છે.